QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#408999 | #7762. 数据库 | kkkgjyismine4 | 20 | 69ms | 8436kb | C++14 | 2.2kb | 2024-05-11 14:53:13 | 2024-05-11 14:53:13 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int inf=1e9;
int h[10005],w[260000],to[260000],nxt[260000],dis[10005],dis1[10005],f[10005],lst[10005],k,s,t,n,m,cnt;
int rot[10005],p[260000],c[260000],x,y,ans,mx;
bool bl[10005];
void jb(int u,int v,int W,int C){
++cnt;w[cnt]=W;c[cnt]=C;
to[cnt]=v;nxt[cnt]=h[u];h[u]=cnt;
}
void JB(int u,int v,int W,int C){
jb(u,v,W,C);jb(v,u,0,-C);
}
queue<int>q;
bool spfa(){
for(int i=1;i<=k;i++) bl[i]=lst[i]=f[i]=0,dis[i]=inf;
dis[s]=0,f[s]=inf;q.push(s);
while(!q.empty()){
int u=q.front();q.pop();
bl[u]=0;
for(int i=h[u];i!=0;i=nxt[i]){
int v=to[i];
if(w[i]>0&&dis[v]>dis[u]+c[i]){
lst[v]=i;
f[v]=min(f[u],w[i]);
dis[v]=dis[u]+c[i];
if(bl[v]==0){
bl[v]=1;
q.push(v);
}
}
}
}
return lst[t]!=0;
}
#define pii pair<int,int>
#define fi first
#define se second
priority_queue<pii>pq;
int mk[10050];
bool dj(){
for(int i=1;i<=k;i++)bl[i]=lst[i]=f[i]=mk[i]=0,dis[i]=inf;
dis[s]=0,f[s]=inf,pq.push(make_pair(-dis[s],s));
while(pq.size()){
pii dog=pq.top();pq.pop();int u=dog.se;
if(mk[u])continue;mk[u]=1;
for(int i=h[u];i!=0;i=nxt[i]){
int v=to[i];
if(w[i]>0)assert(c[i]+dis1[u]-dis1[v]>=0);
if(w[i]>0&&dis[v]>dis[u]+c[i]+dis1[u]-dis1[v]){
lst[v]=i;
f[v]=min(f[u],w[i]);
dis[v]=dis[u]+c[i]+dis1[u]-dis1[v];
pq.push(make_pair(-dis[v],v));
}
}
}dis[t]+=dis1[t];
return lst[t]!=0;
}
int work(){
bool fl=spfa();
for(int i=1;i<=k;++i)dis1[i]=dis[i];
int mncst=0;
while(dj()==1){
mncst+=dis[t]*f[t];
for(int i=t;i!=s;i=to[lst[i]^1]){
w[lst[i]]-=f[t];
w[lst[i]^1]+=f[t];
}
}
return mncst;
}
int N,M,Q;
int Wc[5500],Id[5050],Lst[5050],stk[5050],tail;
int main(){
cnt=1;
cin>>N>>M>>Q;
for(int i=1;i<=N;++i)scanf("%d",&Wc[i]);int ans1=0;
for(int i=1;i<=Q;++i){
scanf("%d",&Id[i]),ans1+=Wc[Id[i]];
if(tail&&stk[tail]==Id[i])ans1-=Wc[Id[i]];
else stk[++tail]=Id[i];
}
Q=tail;for(int i=1;i<=Q;++i)Id[i]=stk[i];
k=t=Q+2,s=Q+1,t=Q+2;int lst1=s;
for(int i=1;i<=Q;++i)JB(lst1,i,M-1,0),lst1=i;
JB(lst1,t,M-1,0);
for(int i=1;i<=Q;++i){
if(Lst[Id[i]])JB(Lst[Id[i]]+1,i,1,-Wc[Id[i]]);
Lst[Id[i]]=i;
}
int ans=work();
printf("%d",ans+ans1);
return 0;
}
详细
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 20
Accepted
time: 69ms
memory: 6188kb
input:
10 3 5000 23077 34848 88221 8067 83132 62621 41320 69146 32971 27594 2 7 5 3 9 6 1 9 4 8 1 8 8 3 6 9 1 7 5 5 6 8 1 3 10 6 8 7 10 2 1 2 6 7 5 5 9 5 7 10 10 6 6 7 2 4 3 1 10 10 5 1 1 6 1 2 8 9 2 5 10 1 10 7 5 5 10 5 2 5 6 10 9 5 6 3 5 3 6 5 7 4 1 5 8 1 1 9 7 1 1 2 1 8 6 2 9 8 4 2 5 4 5 2 10 4 3 6 9 7 ...
output:
100598924
result:
ok single line: '100598924'
Test #2:
score: -20
Runtime Error
input:
10 4 5000 54224 55364 32836 46635 99179 26033 49587 15072 63093 94302 4 7 8 4 1 2 6 3 1 1 6 10 5 7 2 9 3 9 1 5 7 3 8 4 7 2 5 3 5 4 1 6 4 10 4 10 8 1 5 7 9 7 9 1 6 1 10 10 10 5 1 1 3 5 10 1 8 8 6 8 8 10 6 9 7 6 1 1 5 3 10 8 6 5 8 7 5 8 4 8 8 1 8 6 4 5 8 10 7 6 7 2 10 7 10 10 3 1 3 5 5 7 3 2 5 3 1 7 6...
output:
result:
Subtask #2:
score: 20
Accepted
Test #4:
score: 20
Accepted
time: 65ms
memory: 8080kb
input:
10 2 5000 65644 5214 85000 40719 98071 56616 35404 16019 96748 89032 5 9 6 1 3 6 8 10 2 9 1 10 5 9 9 9 2 7 7 7 7 10 5 1 3 10 4 2 5 5 2 8 3 2 1 3 3 6 2 4 5 5 2 5 2 3 4 2 10 1 4 6 10 9 6 4 9 10 5 3 9 7 7 2 1 9 5 8 8 4 8 8 4 5 6 1 3 4 8 10 4 3 6 6 9 2 5 2 8 5 10 4 7 10 3 9 3 2 9 3 10 7 1 3 9 9 3 5 1 3 ...
output:
173524192
result:
ok single line: '173524192'
Test #5:
score: 0
Accepted
time: 46ms
memory: 8436kb
input:
100 2 5000 49570 6371 37107 2261 33457 98048 84700 76277 32602 53831 20995 86351 57905 93492 65198 80688 44394 48442 57924 88655 16250 11904 21033 99426 59241 71456 7697 85276 81310 49884 64543 72091 63969 23936 88032 62420 42269 76663 37639 16930 61480 97674 38809 77434 25043 46618 93378 74399 1031...
output:
231972847
result:
ok single line: '231972847'
Test #6:
score: 0
Accepted
time: 18ms
memory: 6224kb
input:
1000 2 5000 40824 4748 88829 17859 98470 82824 82849 16663 96731 71333 73050 75770 22643 62690 87789 72306 46178 68415 85222 18729 54074 53251 45445 35978 1417 85067 89297 42145 43426 1108 28947 87941 49299 51501 80512 41395 71615 26966 60841 87838 41260 59483 31968 54392 50188 65874 275 38593 32941...
output:
241831233
result:
ok single line: '241831233'
Subtask #3:
score: 0
Runtime Error
Test #7:
score: 0
Runtime Error
input:
5000 15 400 34145 93322 29976 7963 53362 50640 10859 94528 13329 49980 18826 50286 60155 79748 73253 18329 5216 83079 48220 98825 46592 76855 14037 19859 80960 4461 377 70496 28092 99806 5355 27013 92051 95231 65553 32365 3862 89764 86063 93033 12754 68996 38965 52942 69948 34370 3023 52079 16066 57...
output:
result:
Subtask #4:
score: 0
Runtime Error
Test #10:
score: 0
Runtime Error
input:
10 5 1000 86764 81108 88408 93029 87155 18790 28170 29349 81866 77109 8 7 10 7 2 7 1 8 4 10 9 10 4 1 7 1 9 9 1 6 6 1 9 6 7 1 8 10 1 7 9 1 1 9 7 10 8 5 5 1 2 3 10 6 2 6 2 6 1 2 7 8 5 6 10 2 9 8 2 6 8 5 10 8 1 10 4 6 5 6 3 8 1 3 5 2 2 7 2 4 5 5 8 2 4 1 3 6 8 2 2 3 1 8 1 5 8 6 9 7 7 3 7 9 8 9 9 7 5 3 6...
output:
result:
Subtask #5:
score: 0
Skipped
Dependency #1:
0%