QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#26125 | #1269. New Equipments | Wu_Ren | RE | 0ms | 3780kb | C++17 | 1.6kb | 2022-04-06 17:00:38 | 2022-04-29 02:58:49 |
Judging History
answer
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int n,m,a[60],b[60],c[60],v[5060],t=0,head[6010],o,cnt,S,T,pre[6010],lst[6010],cc[6010];
bool vis[6010];
ll dis[6010];
struct edge{
int to,link,w;
ll c;
}e[200000];
void add_edge(int u,int v,int w,ll c){
e[++o]={v,head[u],w,c},head[u]=o;
e[++o]={u,head[v],0,-c},head[v]=o;
}
queue<int>q;
bool spfa(){
for(int i=1;i<=cnt;i++) dis[i]=1e18,pre[i]=lst[i]=0;
dis[S]=0,cc[S]=2e9;
q.push(S),vis[S]=1;
while(q.size()){
int u=q.front();q.pop();
vis[u]=0;
for(int i=head[u],v;i;i=e[i].link) if(dis[v=e[i].to]>dis[u]+e[i].c&&e[i].w){
dis[v]=dis[u]+e[i].c,cc[v]=min(cc[u],e[i].w),pre[v]=u,lst[v]=i;
if(!vis[v]) q.push(v),vis[v]=1;
}
}
return pre[T];
}
void sol(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d%d%d",&a[i],&b[i],&c[i]);
int x=-b[i]/(2*a[i]);
x=max(1,min(x,m));
for(int j=max(1,x-n);j<=min(m,x+n);j++) v[++t]=j;
}
sort(v+1,v+t+1),t=unique(v+1,v+t+1)-v-1;
cnt=n+t,S=++cnt,T=++cnt;
for(int i=1;i<=cnt;i++) head[i]=0;o=1;
for(int i=1;i<=n;i++) add_edge(S,i,1,0);
for(int i=1;i<=t;i++) add_edge(n+i,T,1,0);
for(int i=1;i<=n;i++){
int x=-b[i]/(2*a[i]);
for(int j=max(1,x-n);j<=min(m,x+n);j++) add_edge(i,n+lower_bound(v+1,v+t+1,j)-v,1,1ll*a[i]*j*j+1ll*b[i]*j+c[i]);
}
ll nw=0;
while(spfa()){
int u=T,x=cc[T];
while(x--) printf("%lld ",nw+=dis[T]);
while(u!=S){
e[lst[u]].w-=cc[T];
e[lst[u]^1].w+=cc[T];
u=pre[u];
}
}
puts("");
}
int main(){
int _;
scanf("%d",&_);
while(_--) sol();
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3780kb
input:
1 3 5 2 3 10 2 -3 10 1 -1 4
output:
4 15 37
result:
ok single line: '4 15 37 '
Test #2:
score: -100
Runtime Error
input:
10 50 50 2 -16 79 8 -21 54 8 -1 3 1 -7 47 5 -20 89 1 -2 47 2 -10 26 10 31 28 2 -16 37 6 -16 44 2 -8 100 3 -26 65 3 -6 91 10 -33 56 2 -7 22 2 -12 74 1 -3 7 7 -30 51 1 -4 8 1 -10 62 2 -5 5 1 -3 38 7 -32 57 4 -24 65 1 -8 97 7 -28 71 5 -13 71 2 -14 49 6 -33 100 2 7 69 8 -22 38 5 -23 88 7 20 57 7 -11 83 ...