QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#223739 | #7064. Spy | veg# | TL | 580ms | 24064kb | C++14 | 1.6kb | 2023-10-22 16:21:11 | 2023-10-22 16:21:12 |
Judging History
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 ...