QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#26125#1269. New EquipmentsWu_RenRE 0ms3780kbC++171.6kb2022-04-06 17:00:382022-04-29 02:58:49

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-29 02:58:49]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3780kb
  • [2022-04-06 17:00:38]
  • 提交

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
...

output:


result: