QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#244198 | #7762. 数据库 | zhouhuanyi | 40 | 669ms | 4200kb | C++14 | 2.2kb | 2023-11-08 21:51:51 | 2023-11-08 21:51:52 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<queue>
#define N 5000
#define M 500000
using namespace std;
const int inf=(int)(1e9);
int read()
{
char c=0;
int sum=0;
while (c<'0'||c>'9') c=getchar();
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
struct node
{
int v,data,cost,nxt;
};
node edge[M+1];
struct reads
{
int num;
long long data;
bool operator < (const reads &t)const
{
return data>t.data;
}
};
int n,m,q,s,t,head[N+1],cur[N+1],dis[N+1],w[N+1],ps[N+1],len=1;
long long d[N+1],ans;
bool vis[N+1];
void add(int x,int y,int z,int w)
{
edge[++len]=(node){y,z,w,head[x]},head[x]=len;
edge[++len]=(node){x,0,-w,head[y]},head[y]=len;
return;
}
bool dijkstra()
{
int top;
priority_queue<reads>q;
for (int i=s;i<=t;++i) dis[i]=-inf;
dis[s]=0,q.push((reads){s,0});
while (!q.empty())
{
top=q.top().num,q.pop();
for (int i=head[top];i>0;i=edge[i].nxt)
if (edge[i].data&&dis[edge[i].v]<dis[top]+edge[i].cost+d[top]-d[edge[i].v])
dis[edge[i].v]=dis[top]+edge[i].cost+d[top]-d[edge[i].v],q.push((reads){edge[i].v,dis[edge[i].v]});
}
for (int i=s;i<=t;++i) d[i]+=dis[i];
return dis[t]!=-inf;
}
int dinic(int x,int flow)
{
if (x==t) return flow;
int k;
vis[x]=1;
for (int &i=cur[x];i>0;i=edge[i].nxt)
if (edge[i].data&&!vis[edge[i].v]&&d[edge[i].v]==d[x]+edge[i].cost)
{
k=dinic(edge[i].v,min(flow,edge[i].data));
if (k)
{
edge[i].data-=k,edge[i^1].data+=k,vis[x]=0;
return k;
}
}
vis[x]=0;
return 0;
}
int main()
{
int x,flow;
n=read(),m=read(),q=read(),s=0,t=q;
for (int i=1;i<=n;++i) w[i]=read();
add(0,1,m-1,0);
for (int i=1;i<=q-1;++i) add(i,i+1,inf,0);
for (int i=1;i<=q;++i)
{
x=read();
if (!ps[x]) ans+=w[x];
else if (ps[x]+1<=i-1) add(ps[x]+1,i,1,w[x]),ans+=w[x];
ps[x]=i;
}
for (int i=1;i<=q;++i) d[i]=-inf;
for (int i=0;i<=q;++i)
for (int j=head[i];j>0;j=edge[j].nxt)
if (edge[j].data)
d[edge[j].v]=max(d[edge[j].v],d[i]+edge[j].cost);
while (dijkstra())
{
for (int i=s;i<=t;++i) cur[i]=head[i];
while (flow=dinic(s,inf)) ans-=flow*d[t];
}
printf("%lld\n",ans);
return 0;
}
详细
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 0
Time Limit Exceeded
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:
result:
Subtask #2:
score: 0
Time Limit Exceeded
Test #4:
score: 0
Time Limit Exceeded
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:
result:
Subtask #3:
score: 20
Accepted
Test #7:
score: 20
Accepted
time: 1ms
memory: 4052kb
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:
19341503
result:
ok single line: '19341503'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3800kb
input:
5000 15 400 68511 70579 96844 20943 72871 28340 68790 60294 76760 12623 80406 65418 37942 2849 76307 28818 18555 42151 94506 78241 15350 11345 76323 21860 22703 31009 24763 71007 60858 53746 28720 5027 72512 39122 55299 41675 88475 94331 78711 3464 80345 69031 98746 14792 97862 97255 5853 92742 9096...
output:
19515326
result:
ok single line: '19515326'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
5000 15 400 18305 15347 86331 37503 78391 3378 82447 51150 49032 2422 47659 20516 18666 16520 27948 17865 45842 66799 35584 75288 46358 21654 30233 25291 44810 27579 93986 15174 56012 48286 66826 93615 77979 40669 17262 77857 82134 50752 19642 77961 55856 68600 60598 33035 94214 17392 16736 21460 58...
output:
18253485
result:
ok single line: '18253485'
Subtask #4:
score: 20
Accepted
Test #10:
score: 20
Accepted
time: 310ms
memory: 4200kb
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:
15248002
result:
ok single line: '15248002'
Test #11:
score: 0
Accepted
time: 446ms
memory: 3928kb
input:
10 10 1000 57793 91210 18011 676 38391 78527 56352 69343 95947 5616 5 8 4 5 10 6 1 7 3 10 2 7 1 9 5 3 5 8 3 8 7 10 2 10 6 1 4 3 6 10 6 3 8 4 3 9 1 6 10 3 10 1 6 2 9 9 3 5 8 8 3 9 1 5 9 9 3 3 7 9 2 4 1 9 8 3 1 2 8 9 10 9 4 3 10 5 4 4 8 6 6 9 3 3 2 3 7 2 3 3 10 4 5 5 6 4 2 5 10 1 2 6 9 8 7 9 4 8 2 1 2...
output:
511866
result:
ok single line: '511866'
Test #12:
score: 0
Accepted
time: 343ms
memory: 3964kb
input:
10 15 1000 19536 14188 62086 25660 67447 48774 97871 17167 8671 85361 3 5 2 6 4 6 10 5 7 6 10 8 1 9 5 7 5 5 2 10 7 10 8 6 3 4 2 2 8 9 6 10 9 10 10 9 6 1 7 2 1 10 8 10 3 9 1 8 10 4 6 9 9 8 1 5 2 10 9 1 3 6 5 6 2 5 3 9 6 5 6 10 5 6 10 4 6 6 8 8 9 5 2 10 1 10 7 4 2 6 10 5 6 2 3 1 3 9 8 3 9 7 7 7 2 6 7 ...
output:
446761
result:
ok single line: '446761'
Test #13:
score: 0
Accepted
time: 50ms
memory: 3836kb
input:
100 5 1000 95646 33117 46458 52069 38647 38645 60235 93897 41039 35835 49580 92470 5371 6812 38049 9178 50163 92322 9735 27037 58888 49095 68473 5472 1644 94513 50597 10246 96329 51334 1986 79907 89526 10771 29923 55249 59048 91934 46853 79352 85644 57708 57300 20536 70782 61882 58712 97314 45686 55...
output:
36018137
result:
ok single line: '36018137'
Test #14:
score: 0
Accepted
time: 234ms
memory: 3840kb
input:
100 10 1000 36326 35981 96633 82565 65884 23199 50344 49682 96971 42033 2351 31928 50056 73426 36217 89994 30603 27971 17757 19901 99501 35915 27895 26451 91714 36134 94294 19114 22490 97680 48272 80639 24603 93000 28420 7595 7314 52546 12258 58666 88422 29237 69223 41046 13515 72493 26486 34554 239...
output:
30951978
result:
ok single line: '30951978'
Test #15:
score: 0
Accepted
time: 669ms
memory: 4088kb
input:
100 15 1000 60259 28844 6884 35222 45974 11055 13021 13966 14853 85552 12283 29760 50104 63448 84364 1684 99886 31837 61724 84415 28292 81814 31562 60077 93784 1729 1602 56374 19276 89781 13359 78765 97380 34118 39756 12254 61197 53500 95962 61254 16553 24467 58101 53482 65199 75076 67326 92045 306 ...
output:
26014456
result:
ok single line: '26014456'
Test #16:
score: 0
Accepted
time: 10ms
memory: 3816kb
input:
1000 5 1000 84587 68464 19119 74315 48972 23581 58263 43666 21662 5458 47594 18617 52236 24283 45998 66734 8501 94413 31981 77247 50069 95649 21536 8055 62698 98164 14074 22987 14525 12396 7681 17830 97091 88885 86419 1067 92977 54999 33673 9550 67710 98546 82017 17583 667 36168 61540 74015 42193 48...
output:
45688268
result:
ok single line: '45688268'
Test #17:
score: 0
Accepted
time: 41ms
memory: 4068kb
input:
1000 10 1000 24129 67704 68122 93372 94874 19813 14041 20830 97805 57074 99877 64455 80825 93755 98668 89675 35445 42895 74964 71326 43884 8123 1767 83698 2892 77832 21668 85066 17440 49874 77903 22427 45669 41174 40029 27379 61235 13563 4313 90065 99573 45555 19683 39486 76606 30438 34528 180 83016...
output:
44994110
result:
ok single line: '44994110'
Test #18:
score: 0
Accepted
time: 95ms
memory: 3904kb
input:
1000 15 1000 59991 63683 65484 87716 79869 15955 13746 80474 77381 51499 17028 13036 18275 82716 12845 66038 16310 66787 28778 73107 90796 63216 85094 24799 99979 96956 35994 21067 81494 75695 91088 34745 82075 27522 293 67267 51879 50823 80429 54323 21127 60258 40463 26950 69326 7049 39530 62048 23...
output:
39885004
result:
ok single line: '39885004'
Subtask #5:
score: 0
Skipped
Dependency #1:
0%