QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#223739#7064. Spyveg#TL 580ms24064kbC++141.6kb2023-10-22 16:21:112023-10-22 16:21:12

Judging History

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

  • [2023-10-22 16:21:12]
  • 评测
  • 测评结果:TL
  • 用时:580ms
  • 内存:24064kb
  • [2023-10-22 16:21:11]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
const ll INF=1e18;
using namespace std;

const int N=4e5+5;
int n,cnt,to[N],nxt[N],he[N],pas[N],S,T,pre[N],from[N];
ll b[N],c[N],w[N],dis[N];
bool vis[N];
void Add(int u,int v,int k,ll kk) {
	to[++cnt]=v,nxt[cnt]=he[u],he[u]=cnt;
	w[cnt]=kk,pas[cnt]=k; from[cnt]=u;
}
void add(int u,int v,ll k) {
//	printf("%d %d %d\n",u,v,k);
	Add(u,v,1,k);
	Add(v,u,0,-k);
}
queue<int>q;
bool bfs() {
	for(int i=1;i<=T;++i) dis[i]=INF;
	while(!q.empty()) q.pop();
	q.push(S);
	dis[S]=0,vis[S]=1;
	while(!q.empty()) {
		int u=q.front(); q.pop();
		for(int e=he[u];e;e=nxt[e]) {
			int v=to[e];
			if(dis[v]>dis[u]+w[e]&&pas[e]) {
				dis[v]=dis[u]+w[e]; pre[v]=e;
				if(!vis[v]) {
					vis[v]=1; q.push(v);
				}
			}
		}
		vis[u]=0;
	}
	return dis[T]!=INF;
}
ll ans=0;
void Deal() {
	ll x=INF;
	for(int e=pre[T];e;e=pre[from[e]]) x=min(x,(ll)pas[e]);
	for(int e=pre[T];e;e=pre[from[e]]) {
		pas[e]-=x; pas[e^1]+=x;
		ans+=x*w[e];
	}
}
struct A{ll a; int p;}a[N];
bool cmp(A i,A j) {
	return i.a<j.a;
}
int main() {
	scanf("%d",&n); cnt=1;
	for(int i=1;i<=n;++i) scanf("%lld",&a[i].a);
	for(int i=1;i<=n;++i) scanf("%d",&a[i].p);
	for(int i=1;i<=n;++i) scanf("%lld",&b[i]);
	for(int i=1;i<=n;++i) scanf("%lld",&c[i]);
	sort(c+1,c+n+1);
	sort(a+1,a+n+1,cmp);
	S=n+n+1,T=S+1;
	for(int i=1;i<=n;++i) {
		add(S,i,0); add(i+n,T,0);
		int l=0; ll s=0;
		for(int j=1;j<=n;++j) {
			while(l<=n&&a[l+1].a<b[i]+c[j]) {
				++l; 
				s+=a[l].p;
			}
			add(i,j+n,-s);
		}
	}
	while(bfs()) {
		Deal();
	}
	printf("%lld\n",-ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 20052kb

input:

4
1 2 3 4
1 1 1 1
0 0 1 1
0 1 1 2

output:

3

result:

ok single line: '3'

Test #2:

score: 0
Accepted
time: 567ms
memory: 22352kb

input:

400
1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000...

output:

160000

result:

ok single line: '160000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 22072kb

input:

40
1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 10000000000000000...

output:

1600

result:

ok single line: '1600'

Test #4:

score: 0
Accepted
time: 579ms
memory: 23956kb

input:

400
4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000...

output:

160000

result:

ok single line: '160000'

Test #5:

score: 0
Accepted
time: 577ms
memory: 23916kb

input:

400
-400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -...

output:

0

result:

ok single line: '0'

Test #6:

score: 0
Accepted
time: 570ms
memory: 24064kb

input:

400
41 18467 6334 26500 19169 15724 11478 29358 26962 24464 5705 28145 23281 16827 9961 491 2995 11942 4827 5436 32391 14604 3902 153 292 12382 17421 18716 19718 19895 5447 21726 14771 11538 1869 19912 25667 26299 17035 9894 28703 23811 31322 30333 17673 4664 15141 7711 28253 6868 25547 27644 32662 ...

output:

0

result:

ok single line: '0'

Test #7:

score: 0
Accepted
time: 580ms
memory: 23392kb

input:

400
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

400

result:

ok single line: '400'

Test #8:

score: 0
Accepted
time: 567ms
memory: 22360kb

input:

400
-1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1...

output:

0

result:

ok single line: '0'

Test #9:

score: 0
Accepted
time: 0ms
memory: 20116kb

input:

10
7 7 7 7 7 7 7 7 7 7
1 1 1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2 2 3
4 4 4 4 4 4 4 4 4 3

output:

0

result:

ok single line: '0'

Test #10:

score: 0
Accepted
time: 0ms
memory: 20124kb

input:

2
0 1
1 1
0 1
0 2

output:

3

result:

ok single line: '3'

Test #11:

score: -100
Time Limit Exceeded

input:

400
13847081798897 874663680339 -1528662074038 10439909774959 1822373103148 -6974433017907 6309247250385 11141586625400 16517676644164 -17331800423448 18505534619011 -19766744660346 6180770287595 10091989087414 568941650316 -16088179604413 4394384705024 -12261134024334 5922925172362 -15877810472552 ...

output:


result: