QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #319271 | #5035. foo~ | Harry27182 | 80 | 854ms | 27280kb | C++14 | 2.1kb | 2024-02-02 11:40:23 | 2024-02-02 11:40:23 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int f[35][600005],val1[5005][5005],val2[5005][5005],n,k,a[600005],c[600005],st[600005];
struct segment
{
int tr[2400005],tag[2400005];
void build(int k,int l,int r,int p)
{
tag[k]=0;
if(l==r){tr[k]=f[p-1][l-1];return;}
int mid=(l+r)>>1;
build(k<<1,l,mid,p);build(k<<1|1,mid+1,r,p);
tr[k]=max(tr[k<<1],tr[k<<1|1]);
}
void update(int k,int v){tr[k]+=v;tag[k]+=v;}
void pushdown(int k)
{
if(!tag[k])return;
update(k<<1,tag[k]);update(k<<1|1,tag[k]);
tag[k]=0;
}
void change(int k,int l,int r,int x,int y,int v)
{
if(x<=l&&r<=y){update(k,v);return;}
int mid=(l+r)>>1;pushdown(k);
if(x<=mid)change(k<<1,l,mid,x,y,v);
if(y>mid)change(k<<1|1,mid+1,r,x,y,v);
tr[k]=max(tr[k<<1],tr[k<<1|1]);
}
int query(int k,int l,int r,int x,int y)
{
if(x<=l&&r<=y)return tr[k];
int mid=(l+r)>>1,res=0;pushdown(k);
if(x<=mid)res=max(res,query(k<<1,l,mid,x,y));
if(y>mid)res=max(res,query(k<<1|1,mid+1,r,x,y));
return res;
}
}seg1,seg2;
int solve(int op)
{
if(op==1)reverse(a+1,a+n+1);
if(k==1)
{
int mx=0,res=0,top=0,num=0;
for(int i=1;i<=n;i++)
{
while(top&&a[st[top]]<a[i])top--;
st[++top]=i;res=max(res,top);
}
for(int i=1;i<=n;i++)if(a[i]>mx)mx=a[i],num++;
return max(res,num);
}
for(int i=0;i<=k;i++)for(int j=1;j<=n;j++)f[i][j]=-0x3f3f3f3f;f[0][0]=0;
for(int i=1;i<=k;i++)
{
seg1.build(1,1,n,i);seg2.build(1,1,n,i);
int top=0;
for(int j=1;j<=n;j++)
{
while(top&&a[st[top]]<a[j])seg2.change(1,1,n,1,st[top],-1),top--;
seg2.change(1,1,n,1,j,1);seg1.change(1,1,n,st[top]+1,j,1);
st[++top]=j;
f[i][j]=max(seg1.query(1,1,n,1,j),seg2.query(1,1,n,1,j));
}
}
int res=0;
for(int i=1;i<=n;i++)res=max(res,f[k][i]);
return res;
}
int main()
{
cin.tie(0)->sync_with_stdio(0);
cin>>n>>k;int p=0,ans=0;
for(int i=1;i<=n;i++)
{
cin>>c[i];
if(c[i]==n)p=i;
}
for(int i=1;i<=n;i++)a[i]=c[(i+p-2)%n+1];
ans=max(ans,solve(0));
for(int i=1;i<=n;i++)a[i]=c[(i+p-1)%n+1];
ans=max(ans,solve(1));
cout<<ans;
return 0;
}
详细
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 1ms
memory: 3644kb
input:
23 6 16 20 22 4 21 10 3 7 5 8 15 12 9 1 6 17 23 13 11 19 18 14 2
output:
20
result:
ok "20"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
13 6 13 9 3 4 12 6 5 1 8 10 11 7 2
output:
13
result:
ok "13"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3756kb
input:
25 3 25 2 3 19 5 6 7 11 8 10 9 20 4 14 21 1 17 12 13 18 15 22 23 16 24
output:
16
result:
ok "16"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3696kb
input:
25 9 1 11 10 23 9 24 7 8 19 3 5 21 18 12 15 16 17 13 2 20 14 22 4 6 25
output:
23
result:
ok "23"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
13 2 1 4 2 3 5 6 7 8 9 10 12 11 13
output:
12
result:
ok "12"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
17 5 4 2 3 6 5 1 7 8 13 16 11 12 9 14 15 10 17
output:
15
result:
ok "15"
Test #7:
score: 0
Accepted
time: 1ms
memory: 3572kb
input:
8 2 1 2 5 6 3 4 7 8
output:
8
result:
ok "8"
Test #8:
score: 0
Accepted
time: 1ms
memory: 3672kb
input:
11 5 3 11 2 10 6 5 1 4 8 7 9
output:
11
result:
ok "11"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
10 1 5 3 4 1 10 8 9 6 7 2
output:
6
result:
ok "6"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
16 2 15 12 14 9 11 13 1 3 10 8 5 2 16 4 6 7
output:
9
result:
ok "9"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
6 3 4 1 5 6 2 3
output:
6
result:
ok "6"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
1 1 1
output:
1
result:
ok "1"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
16 5 7 14 13 16 10 1 9 11 3 8 2 4 5 15 12 6
output:
14
result:
ok "14"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
10 3 10 1 7 2 8 6 9 5 4 3
output:
9
result:
ok "9"
Test #15:
score: 0
Accepted
time: 1ms
memory: 3776kb
input:
23 9 12 11 22 2 5 9 1 4 18 19 17 16 23 20 6 13 8 21 10 7 14 15 3
output:
23
result:
ok "23"
Test #16:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
15 4 4 3 8 13 12 1 14 9 15 10 7 11 2 6 5
output:
13
result:
ok "13"
Test #17:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
24 7 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
output:
24
result:
ok "24"
Test #18:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
4 2 1 2 3 4
output:
4
result:
ok "4"
Test #19:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
18 1 1 3 5 7 9 11 13 15 17 18 16 14 12 10 8 6 4 2
output:
10
result:
ok "10"
Test #20:
score: 0
Accepted
time: 1ms
memory: 3688kb
input:
18 2 1 3 5 7 9 11 13 15 17 18 16 14 12 10 8 6 4 2
output:
18
result:
ok "18"
Subtask #2:
score: 10
Accepted
Test #21:
score: 10
Accepted
time: 3ms
memory: 4392kb
input:
93943 1 87243 48984 50611 19218 77699 25025 85769 28141 13380 34875 42459 66419 53472 4367 48292 16894 92171 87263 42527 67085 30687 29235 27515 81053 31421 34864 83591 70491 75344 7026 50250 63402 26773 5330 36308 76399 80032 15501 16205 71750 73964 67876 68901 70548 2043 79979 89479 19784 38838 44...
output:
25
result:
ok "25"
Test #22:
score: 0
Accepted
time: 8ms
memory: 4564kb
input:
112118 1 24338 1586 3 108269 5 53472 80391 70331 9 15335 62487 28331 13 14 16564 94323 36681 108815 32632 44382 21 22 23 24 11758 40070 21518 51991 109983 30 45524 59784 33 2068 62111 36 37 38 39 89031 30508 42 43 16414 110006 34303 47 10331 44651 50 93957 95407 22019 88681 56605 12426 28498 58 59 8...
output:
281
result:
ok "281"
Test #23:
score: 0
Accepted
time: 30ms
memory: 6724kb
input:
391400 1 158965 280194 3 4 5 369036 92293 245923 57403 10 6887 280754 277300 110148 314164 135940 17 46573 126951 111447 301107 22 23 24 25 26 247952 28 342994 339309 23647 350245 33 299608 35 36 37 263236 232063 40 41 42 43 44 39280 46 299122 11961 380375 384513 51 318009 162567 54 55 56 27356 58 6...
output:
693
result:
ok "693"
Test #24:
score: 0
Accepted
time: 29ms
memory: 7024kb
input:
440571 1 243784 2 3 130039 61385 6 7 8 244611 260729 29014 12 326371 416098 15 293728 182717 66822 387603 156910 225815 413135 171756 315815 26444 302419 384825 37746 17634 391896 354575 426625 290920 34 49456 36 161212 212843 39 40 41 436888 43 102088 405279 46 47 77451 49 50 368530 52402 34143 54 ...
output:
665
result:
ok "665"
Test #25:
score: 0
Accepted
time: 17ms
memory: 5532kb
input:
237580 1 1 2 3 4 5 45736 171997 8 235046 10 11 186778 13 14 15 16 17 18 19 20 21 22 23 91724 25 147783 27 125261 29 30 27556 32 108919 76675 35 36 18966 212471 100584 11715 204252 77843 43 176763 18552 46 82644 48 49 50 51 191552 53 232631 160703 114013 69672 75193 59 60 207114 62 63 167312 83372 66...
output:
890
result:
ok "890"
Test #26:
score: 0
Accepted
time: 0ms
memory: 4480kb
input:
108629 1 1 2 3 35575 5 7205 104276 8 9 10 104552 12 13 99818 15 16 17 18 19 16579 21 74459 23 24 25 98758 27 30553 28622 105401 31 32 33 98277 29214 36 37 38 34671 99851 41 42 20159 65626 49334 58829 47 48 15553 50 16448 157 96610 71139 51449 24593 66195 11741 5738 45685 61 76006 91433 64 13205 66 6...
output:
549
result:
ok "549"
Test #27:
score: 0
Accepted
time: 1ms
memory: 3660kb
input:
7474 1 6087 2 3 3276 2246 1022 4790 8 9 10 11 3555 13 14 5187 16 17 18 5222 2852 21 3905 23 2069 25 26 27 6248 29 30 31 32 33 3467 35 5413 37 38 39 40 41 42 43 44 45 46 47 6366 6217 6683 4855 86 6754 7423 55 56 3421 58 7129 6415 2719 964 63 7191 6681 5871 2830 68 1114 70 71 4387 73 74 75 76 77 394 7...
output:
117
result:
ok "117"
Test #28:
score: 0
Accepted
time: 25ms
memory: 6284kb
input:
327474 1 210193 138271 6815 114087 210548 236834 247829 287541 142327 57519 226037 185228 4602 111639 172642 13926 122775 323427 276201 198051 175153 262523 182602 84772 315273 161585 146845 231049 98201 170526 58890 213780 86346 161912 320369 55154 202159 224318 92082 314469 92925 225630 89586 2190...
output:
31
result:
ok "31"
Test #29:
score: 0
Accepted
time: 14ms
memory: 4988kb
input:
170736 1 1312 68283 94512 153956 14227 44793 18760 153190 59267 3745 39898 34452 88526 153153 151245 72089 72230 139449 97869 105574 61308 52310 63909 66185 76461 57922 15750 32965 63821 123214 62562 154258 26229 154847 29694 20613 163634 112566 78733 77415 148297 8311 18695 146847 137996 128167 946...
output:
27
result:
ok "27"
Test #30:
score: 0
Accepted
time: 2ms
memory: 4168kb
input:
70972 1 42126 45376 26395 39090 6557 69493 22740 10263 3057 30503 16364 27796 52951 62922 17830 66723 34385 8039 28194 11087 10500 9835 5892 8917 21894 16673 49698 55082 66683 54472 60557 6953 739 65333 59825 23918 39644 59672 59765 31158 30188 37359 60653 64449 28747 7064 53759 15156 11687 33993 33...
output:
25
result:
ok "25"
Test #31:
score: 0
Accepted
time: 32ms
memory: 7348kb
input:
471980 1 315450 386066 223827 468592 231628 77257 181339 466496 85446 27241 269600 85959 141799 29249 162311 264524 137245 205794 349273 166576 131873 5521 368496 302373 19082 283842 82343 281817 25429 161084 307699 192224 143156 188759 279732 138312 341989 400389 280646 404120 362537 182646 194306 ...
output:
32
result:
ok "32"
Test #32:
score: 0
Accepted
time: 8ms
memory: 5380kb
input:
141837 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100...
output:
141837
result:
ok "141837"
Test #33:
score: 0
Accepted
time: 3ms
memory: 4200kb
input:
48198 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...
output:
48198
result:
ok "48198"
Test #34:
score: 0
Accepted
time: 2ms
memory: 3924kb
input:
28730 1 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 101 103 105 107 109 111 113 115 117 119 121 123 125 127 129 131 133 135 137 139 141 143 145 147 149 151 153 155 157 159 161 163 165 167 169 171 173...
output:
14366
result:
ok "14366"
Test #35:
score: 0
Accepted
time: 5ms
memory: 4508kb
input:
89450 1 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 101 103 105 107 109 111 113 115 117 119 121 123 125 127 129 131 133 135 137 139 141 143 145 147 149 151 153 155 157 159 161 163 165 167 169 171 173...
output:
44726
result:
ok "44726"
Subtask #3:
score: 20
Accepted
Test #36:
score: 20
Accepted
time: 28ms
memory: 4072kb
input:
1992 25 144 612 1315 1966 1779 1773 1529 625 36 1849 1783 1441 1388 1558 1258 724 137 397 542 353 1162 1213 406 792 1317 882 994 298 1864 1969 103 449 508 1501 89 1721 195 778 657 222 1152 1780 613 743 1206 694 829 142 69 1973 1465 1343 655 1540 155 146 350 491 759 1695 1082 1357 1329 1745 232 1850 ...
output:
237
result:
ok "237"
Test #37:
score: 0
Accepted
time: 19ms
memory: 3948kb
input:
1992 17 785 891 1027 155 773 587 1829 255 1239 1893 1854 158 349 370 1134 1739 1186 11 1099 1149 481 361 1101 1359 1773 1568 157 1011 79 555 254 285 1260 1722 1684 577 1054 1932 590 1804 414 1415 376 1699 26 971 1554 1504 1987 1327 1184 610 652 1432 206 129 315 1390 1946 64 910 962 1189 326 497 1580...
output:
172
result:
ok "172"
Test #38:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
46 11 41 44 2 9 30 46 28 14 12 20 38 37 19 6 13 7 26 4 34 15 32 5 35 1 25 8 29 45 31 22 18 24 33 42 21 17 39 10 43 11 23 27 36 3 40 16
output:
38
result:
ok "38"
Test #39:
score: 0
Accepted
time: 1ms
memory: 3720kb
input:
53 18 29 23 32 11 24 27 28 16 6 9 3 20 8 38 43 49 18 26 41 53 31 19 48 34 44 52 45 5 30 17 2 13 15 40 1 50 21 14 4 22 51 35 39 7 47 25 10 12 33 42 36 46 37
output:
49
result:
ok "49"
Test #40:
score: 0
Accepted
time: 1ms
memory: 3704kb
input:
55 25 42 41 51 1 6 49 28 12 33 23 31 47 19 24 48 21 54 16 14 3 26 43 18 5 45 29 50 15 44 35 7 40 9 53 10 32 17 36 4 34 20 38 37 8 55 2 11 39 30 22 52 27 13 46 25
output:
55
result:
ok "55"
Test #41:
score: 0
Accepted
time: 1ms
memory: 3700kb
input:
78 9 44 4 68 49 20 16 67 3 70 40 25 6 46 27 65 10 77 55 12 78 2 31 22 71 74 30 41 53 34 47 32 36 57 19 18 1 26 69 11 52 72 14 8 17 56 51 42 43 62 58 35 76 66 23 54 73 63 75 39 37 28 5 9 24 21 48 64 61 29 45 38 13 59 50 15 7 33 60
output:
42
result:
ok "42"
Test #42:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
17 2 11 4 3 1 5 14 17 8 7 6 2 16 9 10 13 15 12
output:
12
result:
ok "12"
Test #43:
score: 0
Accepted
time: 19ms
memory: 4016kb
input:
1998 17 333 1769 698 1064 655 451 102 8 1306 1092 213 750 1963 1122 759 890 1170 1700 87 820 175 196 1617 370 1693 1993 1927 851 832 864 299 607 1174 1994 1584 1962 1047 1000 1829 164 209 649 942 660 118 1010 1114 1291 1418 1819 540 1861 536 1745 328 1358 1394 677 59 1842 578 257 1776 770 1850 783 9...
output:
172
result:
ok "172"
Test #44:
score: 0
Accepted
time: 13ms
memory: 3900kb
input:
1995 11 781 851 1465 1961 351 876 477 1746 14 1703 68 983 1857 87 551 1314 1877 978 1821 606 244 1269 1638 1062 952 586 735 1302 1190 1644 1554 1328 1614 257 1306 1964 1232 1005 382 335 680 1725 530 1253 903 361 979 1174 1813 1811 557 1123 1580 1445 595 1098 318 1192 1406 297 463 1837 1271 325 1990 ...
output:
126
result:
ok "126"
Test #45:
score: 0
Accepted
time: 18ms
memory: 3916kb
input:
1998 20 344 764 1060 1773 951 1962 1555 1410 1263 985 1665 1666 1010 816 1462 181 1208 1574 142 583 338 1026 1336 1323 1787 134 1397 1177 1632 1445 632 871 1180 1171 716 681 1014 478 1068 1678 620 1379 1799 1256 124 569 112 1432 499 1832 1235 492 690 485 335 1860 1976 1325 1667 1505 1723 1851 1598 9...
output:
199
result:
ok "199"
Test #46:
score: 0
Accepted
time: 16ms
memory: 3912kb
input:
1996 14 1647 582 573 13 273 1391 1373 1996 1526 191 605 1254 1943 1108 1264 1306 1120 642 832 1826 1301 557 761 1170 1117 1688 982 1153 863 1879 1433 1533 981 1570 789 561 189 1830 1075 276 1444 522 168 1595 1140 1522 1532 1314 930 161 478 468 928 1850 439 681 1781 96 1836 446 669 1545 138 1040 180 ...
output:
161
result:
ok "161"
Test #47:
score: 0
Accepted
time: 6ms
memory: 3828kb
input:
1991 5 1932 254 1190 786 1024 1473 617 1462 790 1056 928 1627 1149 1452 300 957 336 1720 1157 592 1241 1750 391 1092 1007 1710 1250 362 127 655 433 876 1776 359 559 109 1053 1267 674 776 1238 1132 1060 608 988 1411 565 1868 1290 1025 1929 1712 1120 1066 1208 1940 1011 1648 980 330 397 1646 360 118 1...
output:
65
result:
ok "65"
Test #48:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
1999 2 860 1838 1580 1476 996 1339 706 873 1880 1600 1240 1220 1243 232 1690 629 217 1944 1284 1829 1693 749 1298 1342 1045 964 1910 638 697 219 420 1343 681 880 302 1224 1621 521 1988 89 1534 1514 655 1983 1574 1091 410 1881 1842 1062 1496 1739 1194 200 386 936 16 242 1513 187 1025 949 1377 589 180...
output:
33
result:
ok "33"
Test #49:
score: 0
Accepted
time: 31ms
memory: 4168kb
input:
1993 28 1506 46 293 1509 509 379 1928 76 381 1745 1712 805 1172 1908 696 362 1927 1892 1822 534 1233 1665 1100 664 1060 1458 1381 93 119 82 43 292 1360 996 907 1586 1022 1757 1482 1545 1406 303 338 1876 1635 611 1645 1485 1862 218 1303 1002 156 1649 951 1981 1992 1349 305 978 531 1195 1693 1370 1541...
output:
269
result:
ok "269"
Test #50:
score: 0
Accepted
time: 4ms
memory: 3872kb
input:
1996 3 1104 382 1454 599 258 1354 486 1288 1375 1677 413 695 1485 1733 1962 1338 13 17 150 629 937 948 1181 698 141 966 1207 286 651 434 165 519 180 1542 1009 766 1344 1112 1178 1074 1487 1944 1722 1603 1165 648 1054 1568 997 1103 1062 874 1448 750 84 1920 1898 77 1410 388 439 1996 172 807 1647 39 1...
output:
42
result:
ok "42"
Subtask #4:
score: 20
Accepted
Dependency #1:
100%
Accepted
Dependency #3:
100%
Accepted
Test #51:
score: 20
Accepted
time: 32ms
memory: 4148kb
input:
4024 15 1966 1244 3820 1634 1680 2982 3208 338 3458 1278 1663 677 694 3571 1416 2596 3369 201 577 57 3615 2954 385 602 1726 3718 903 3689 803 3000 2137 1690 709 3825 1164 2922 2270 2116 1455 2987 2587 2346 1804 1533 2673 1030 144 2297 3578 3784 2810 1792 1811 3737 2615 3729 2941 1161 2586 907 539 14...
output:
180
result:
ok "180"
Test #52:
score: 0
Accepted
time: 50ms
memory: 4380kb
input:
4572 18 1 4278 3 3749 1981 1801 2351 3247 247 1691 3511 620 13 1800 541 2023 3575 18 526 20 1154 22 2012 24 1655 264 1061 28 29 2202 4307 32 3418 3929 2167 36 37 38 39 40 41 859 43 1431 1682 3258 1147 3638 49 156 743 3225 53 54 55 4099 408 4469 1226 1462 1799 3981 3948 64 65 3386 644 68 3021 2703 71...
output:
411
result:
ok "411"
Test #53:
score: 0
Accepted
time: 7ms
memory: 4012kb
input:
4760 2 1 1962 4349 1537 1669 6 7 8 9 1273 3047 781 13 3338 1618 474 437 18 1466 3000 3392 22 1541 2898 25 946 3557 896 845 30 4323 32 33 3212 2971 1896 541 3170 3666 1067 2436 4334 43 2429 45 4431 1109 813 1510 1878 51 52 1988 2023 55 3565 57 2419 4688 3727 3125 693 4585 64 65 1914 67 140 2478 2347 ...
output:
57
result:
ok "57"
Test #54:
score: 0
Accepted
time: 10ms
memory: 3840kb
input:
1440 13 1 2 3 42 5 6 84 288 1427 1308 1146 861 1006 14 17 258 1416 314 337 20 735 22 1145 1123 1316 26 27 932 1315 550 600 640 33 432 35 531 701 38 971 899 1113 4 43 44 45 87 1407 653 976 50 802 239 1180 1202 195 679 57 58 1360 60 610 1015 1115 64 65 828 803 417 69 70 71 1121 73 257 75 76 281 567 28...
output:
202
result:
ok "202"
Test #55:
score: 0
Accepted
time: 63ms
memory: 4444kb
input:
4788 22 1 2 459 4 389 6 3335 4488 9 4350 218 3346 13 2775 15 16 17 18 19 2440 21 47 2187 4594 25 2223 27 937 29 30 471 32 33 185 4014 36 3045 38 2257 40 41 451 43 1497 45 3364 22 48 2376 50 51 52 955 85 1651 56 2225 58 2711 60 4042 2957 63 2860 65 3595 67 68 69 70 1147 72 1269 1045 2348 76 2982 78 7...
output:
715
result:
ok "715"
Test #56:
score: 0
Accepted
time: 24ms
memory: 4064kb
input:
4059 10 1 2 3 4 2713 3050 1171 2873 9 10 3333 1866 13 3439 15 2844 17 1309 2904 2173 3993 22 3553 24 25 26 27 2135 1890 742 2133 32 33 2802 95 36 37 38 39 1987 176 42 43 3556 45 46 47 48 49 50 51 52 53 54 1520 2475 57 58 59 2658 61 62 63 1546 852 1745 67 2140 69 70 657 942 73 74 75 76 77 78 1487 80 ...
output:
431
result:
ok "431"
Test #57:
score: 0
Accepted
time: 11ms
memory: 3852kb
input:
3051 6 1463 2 3 837 5 6 7 8 1307 2826 11 139 13 14 15 620 1015 18 19 2320 2756 690 23 389 2329 26 1919 28 2824 32 2611 30 1482 2700 727 465 37 931 39 40 41 3003 1155 44 45 46 47 48 49 50 1670 2942 1501 54 55 56 57 58 1713 60 832 62 128 64 65 1299 67 190 69 70 71 2940 2449 74 75 1576 556 78 2482 1767...
output:
297
result:
ok "297"
Test #58:
score: 0
Accepted
time: 19ms
memory: 3936kb
input:
1704 24 1145 844 1271 227 700 1178 167 874 1657 1368 1116 1304 705 1390 123 1687 62 147 627 952 128 1231 750 120 775 984 485 546 195 834 182 395 18 622 848 1222 415 1533 805 1404 404 560 165 1193 492 1488 712 434 954 1246 207 1435 1370 459 837 1492 64 1491 1415 914 1493 1325 692 1141 881 1529 1549 2...
output:
221
result:
ok "221"
Test #59:
score: 0
Accepted
time: 6ms
memory: 4012kb
input:
4169 2 1467 3699 2796 3828 2958 537 3803 625 809 472 341 1990 2244 1018 4158 2250 1449 2792 2607 205 2263 1090 21 1940 3976 1803 1775 3237 96 1798 2846 3955 1101 3570 1249 1821 268 2203 3232 3126 1416 2301 1259 3311 666 2104 2820 2338 2858 1754 2489 2790 2247 1228 961 1600 1156 3276 1175 3097 1371 5...
output:
35
result:
ok "35"
Test #60:
score: 0
Accepted
time: 64ms
memory: 4328kb
input:
3701 29 2878 3264 3586 2297 12 456 2203 3347 2751 3616 847 3424 1877 2520 2860 3247 589 3415 3300 3648 1028 1578 1699 156 1328 2468 2335 207 1917 3095 241 2459 2252 2201 3260 753 3154 324 2278 926 453 1689 3392 812 1886 850 251 1276 163 3249 3410 2150 951 1524 1503 2685 2950 646 2541 1590 216 3344 1...
output:
302
result:
ok "302"
Test #61:
score: 0
Accepted
time: 4ms
memory: 3860kb
input:
604 13 200 6 493 545 206 511 83 311 236 247 377 376 37 178 277 92 561 475 187 262 149 463 127 164 473 313 329 161 95 26 320 87 299 184 459 422 185 309 117 458 485 495 450 547 141 211 598 415 136 447 119 400 284 442 553 297 554 578 106 227 207 406 512 541 190 258 552 99 451 246 7 410 145 449 398 389 ...
output:
116
result:
ok "116"
Test #62:
score: 0
Accepted
time: 25ms
memory: 4124kb
input:
1558 30 1245 1469 1511 344 1200 1403 283 703 1257 616 1249 818 1002 508 1329 1294 1079 104 788 614 391 1099 846 448 1454 716 1516 1336 1536 64 758 11 1190 1518 1180 959 925 1236 1458 405 643 656 676 1341 151 654 1181 1395 1012 634 357 1102 513 160 256 981 1475 476 874 1307 85 1037 617 1072 1417 61 1...
output:
261
result:
ok "261"
Test #63:
score: 0
Accepted
time: 53ms
memory: 4324kb
input:
4810 18 1370 1518 3911 2154 1851 2253 3900 3970 3066 240 3699 742 2056 2532 2888 4168 1190 1997 1687 4714 1212 263 1513 4102 465 997 200 1114 224 1708 4281 4329 3506 1659 2055 1894 1730 3522 3406 459 1076 3772 1807 1814 3339 2155 3966 1745 624 2719 4648 267 3509 3082 2683 2613 1340 501 2413 3372 343...
output:
213
result:
ok "213"
Test #64:
score: 0
Accepted
time: 15ms
memory: 3968kb
input:
3592 7 673 3532 805 3479 2792 2409 2175 2701 1366 3096 2046 839 1368 1852 3437 3021 2144 2933 2836 1632 1488 1100 1916 3208 1607 2906 2216 1533 2993 281 2333 2917 493 142 171 2412 3384 151 61 621 1084 764 2643 2461 1918 1943 1869 1174 1241 3403 2871 1040 1113 2152 247 494 1087 1349 963 190 2437 2193...
output:
97
result:
ok "97"
Test #65:
score: 0
Accepted
time: 55ms
memory: 4324kb
input:
4984 18 2804 3306 2999 4476 3060 2753 1687 4513 3468 900 3581 2425 1332 894 4846 2388 728 2025 4583 4177 4587 3167 766 1602 3678 4968 2135 68 1551 808 234 601 1375 4042 3914 275 4348 3927 1676 734 1538 3937 1905 3439 438 4242 2039 2523 1145 943 3659 3984 1815 3347 2047 4216 2110 1293 213 3529 3634 2...
output:
221
result:
ok "221"
Test #66:
score: 0
Accepted
time: 25ms
memory: 4064kb
input:
2297 19 1758 1422 1308 1147 527 505 621 1383 287 717 1600 2287 734 2122 995 1650 2178 999 1066 2130 2151 1641 195 1335 1298 2187 1886 2119 250 606 96 518 308 966 2034 781 2266 116 2164 1205 1442 483 890 44 1644 1256 370 1351 25 1878 258 1450 91 1606 2137 1822 1084 1230 835 670 2020 1249 2167 1523 18...
output:
203
result:
ok "203"
Test #67:
score: 0
Accepted
time: 13ms
memory: 4056kb
input:
3559 7 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...
output:
3559
result:
ok "3559"
Test #68:
score: 0
Accepted
time: 44ms
memory: 4420kb
input:
4288 21 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...
output:
4288
result:
ok "4288"
Test #69:
score: 0
Accepted
time: 20ms
memory: 4012kb
input:
4009 8 4008 4009 4007 540 976 2783 1986 2755 1287 1769 2846 1525 2276 3018 1749 1580 1282 2700 2489 2300 3896 2810 397 259 2922 567 1573 1552 923 2814 2879 707 1009 860 2536 2764 2945 3227 167 1350 2857 2078 3145 462 1341 1147 2049 1663 85 1906 568 2395 2728 3657 352 1022 2584 913 1571 499 2351 1106...
output:
116
result:
ok "116"
Test #70:
score: 0
Accepted
time: 49ms
memory: 4380kb
input:
4801 18 4800 4801 4799 4439 315 737 3783 141 925 4166 4388 484 3480 3410 356 2794 2286 4281 3912 2908 1998 953 3684 4331 3049 4049 2109 3453 3360 4112 3347 2496 245 1436 25 4720 168 2871 1108 3191 1150 1473 3948 3046 2377 292 128 3836 2709 2451 1667 4167 3831 560 2741 4144 2459 577 3335 4619 3251 37...
output:
217
result:
ok "217"
Subtask #5:
score: 20
Accepted
Dependency #4:
100%
Accepted
Test #71:
score: 20
Accepted
time: 462ms
memory: 7700kb
input:
24258 28 16195 14873 33 20006 1896 3981 12124 22472 12277 6101 3559 6639 14935 11928 19344 3302 16586 6903 10338 17710 19716 18018 6246 11333 23567 20753 10585 1582 11474 3359 20357 13618 21666 20150 2028 1688 22377 4728 5493 13805 19466 18819 5193 22600 10853 20085 47 9955 20582 13589 4626 11433 23...
output:
413
result:
ok "413"
Test #72:
score: 0
Accepted
time: 49ms
memory: 4232kb
input:
3156 27 445 103 37 1677 5 1947 7 8 1691 10 11 1406 13 14 1394 16 2369 292 19 2394 2212 22 2144 2428 25 26 1105 149 127 2175 442 32 33 573 2261 1956 903 38 39 40 41 1509 740 975 45 1734 47 48 1445 2634 898 52 1844 602 55 56 2865 58 595 861 182 2231 1605 2427 774 2240 2089 2468 1321 70 71 1263 2815 27...
output:
406
result:
ok "406"
Test #73:
score: 0
Accepted
time: 375ms
memory: 8356kb
input:
41178 13 8425 2 3 4 5 6 19390 26907 3622 10 32560 12 15978 23241 16104 8542 398 16767 26810 32686 21 40230 27390 34359 21750 26793 32491 22256 27250 25068 21940 28325 40332 8054 25231 36 37 38 39 14380 24107 33145 43 44 45 46 36972 48 49 28416 12079 12444 53 54 6168 56 26529 58 59 15989 24997 23328 ...
output:
686
result:
ok "686"
Test #74:
score: 0
Accepted
time: 421ms
memory: 8564kb
input:
48172 12 1 2535 3 4 5 46640 41991 30108 32240 37217 11 2161 34351 2669 30969 30285 38372 4777 19 4204 21 22 45173 24 6616 28543 27 15731 9792 43631 13959 32 38713 6329 47486 26638 37 5311 39 5338 5404 42 43 33271 45 21708 24996 12181 47728 5527 7000 16661 40503 34647 55 33106 57 23527 3642 14248 390...
output:
642
result:
ok "642"
Test #75:
score: 0
Accepted
time: 19ms
memory: 4160kb
input:
7162 4 1 498 3 4 5 6 7 8 9 10 11 12 5697 14 15 16 2016 18 19 20 5858 22 850 24 2141 4198 27 2524 5608 30 31 32 33 34 35 1794 37 38 39 40 41 401 43 652 4854 46 6979 48 6643 50 4676 2447 53 54 55 4388 4353 51 59 60 5089 2960 63 64 65 5748 67 68 69 70 71 6524 2183 74 75 2498 77 887 2489 6307 81 4139 83...
output:
350
result:
ok "350"
Test #76:
score: 0
Accepted
time: 657ms
memory: 9928kb
input:
39950 23 4812 1856 3 35730 28893 6 38841 8 6149 10 11 4584 13 33130 15325 16 17 18 19 13038 21 31497 23 24 25 34094 29410 3358 29 30 31 32 33 34 35 36 37 38 37474 25171 41 42 43 44 10303 3393 1 48 16141 9152 51 52 53 54 28662 14656 57 58 30254 60 61 8567 28390 64 65 66 37732 68 69 70 71 3303 73 74 7...
output:
1898
result:
ok "1898"
Test #77:
score: 0
Accepted
time: 76ms
memory: 5332kb
input:
18719 6 1 2 18558 1548 10235 6 7 8 9 10 11 12 13 14 7425 10806 12782 18 19 8889 21 22 5096 200 25 26 27 3724 29 30 31 32 33 5363 35 1939 37 38 18316 40 41 3092 43 44 45 16065 7170 5483 17242 50 51 52 53 5700 4993 15478 57 58 59 60 61 62 63 8809 65 66 67 68 69 443 71 7121 73 14137 75 76 5912 9097 79 ...
output:
856
result:
ok "856"
Test #78:
score: 0
Accepted
time: 379ms
memory: 7200kb
input:
29580 18 14519 6399 18739 15980 12705 6533 2801 6584 4323 9308 16421 28784 8987 7931 15263 19253 22842 10800 26480 1468 12254 4140 23786 12144 22398 2302 11446 21712 7086 27483 398 18793 28098 5912 1115 5020 7035 13954 1855 12404 21961 22937 7844 11902 24727 25544 87 5292 8586 18210 5009 10139 22864...
output:
302
result:
ok "302"
Test #79:
score: 0
Accepted
time: 14ms
memory: 4348kb
input:
10018 2 25 4540 8967 2333 4043 8904 8482 235 7570 8778 2362 5430 8192 7331 7604 7867 5415 7448 8010 5465 5025 8054 8951 8623 7014 7669 1356 5632 4081 3921 933 227 6349 8798 6205 9285 182 6015 3076 6959 6650 7305 4860 3824 8883 6488 8503 3319 8296 6263 4131 5613 682 4434 7657 4459 6539 5393 948 4403 ...
output:
39
result:
ok "39"
Test #80:
score: 0
Accepted
time: 121ms
memory: 5820kb
input:
28932 6 3089 18681 1254 9140 2854 24238 19780 19149 22279 687 19608 17644 6984 3881 4210 24404 19264 10701 22925 19183 5240 7945 20476 7232 23630 28074 22046 13011 16764 15838 21817 11790 23126 9858 14253 16674 17952 21204 27548 28854 2686 3037 22513 6678 14241 1981 23540 24564 24237 17967 22606 160...
output:
117
result:
ok "117"
Test #81:
score: 0
Accepted
time: 2ms
memory: 3844kb
input:
1203 2 759 211 717 650 1094 319 606 172 359 464 112 259 305 372 608 400 684 385 296 263 707 142 175 841 40 353 553 732 824 529 1009 51 1004 1190 628 1058 1145 883 625 477 842 927 821 202 660 76 457 97 765 906 365 442 488 412 301 378 940 1175 817 429 762 928 819 479 24 189 600 662 695 1184 1158 1151 ...
output:
29
result:
ok "29"
Test #82:
score: 0
Accepted
time: 451ms
memory: 8620kb
input:
35579 18 19170 25227 4776 24924 10922 1445 3003 7913 31734 19041 35050 25211 25419 25806 18536 33556 7340 6806 27293 17703 17665 136 22870 28353 4712 23075 9259 3916 9834 2690 13323 12163 8248 32847 479 3387 16065 34090 32504 5285 5844 15382 25020 9876 3433 25522 34519 9192 11429 12714 29683 30415 2...
output:
314
result:
ok "314"
Test #83:
score: 0
Accepted
time: 152ms
memory: 5336kb
input:
8475 29 7682 887 7496 806 8283 1332 2273 2312 2678 6892 422 7867 237 7582 489 1014 1482 61 1518 254 4434 6069 4802 2834 1438 4788 6305 5925 3037 5046 7677 6081 7155 1071 2382 2452 6260 4931 4352 7627 4761 7041 5962 2798 6405 1481 1174 5392 7360 6915 2319 2863 1817 1834 3302 6985 8162 2384 1133 1208 ...
output:
363
result:
ok "363"
Test #84:
score: 0
Accepted
time: 41ms
memory: 4280kb
input:
2836 25 1543 1390 2556 161 1058 413 1847 947 2058 2805 1819 848 1635 2579 1409 1239 450 2248 1161 2007 515 1218 2491 1358 1383 1227 789 1138 1253 1177 397 2534 2320 2105 209 1430 742 1150 2074 811 855 1844 1410 1814 1664 1307 1188 2833 1483 611 2457 546 2727 1662 974 2131 843 2715 1973 1505 1275 753...
output:
259
result:
ok "259"
Test #85:
score: 0
Accepted
time: 582ms
memory: 9508kb
input:
44426 18 32852 42617 3656 30129 32589 19100 24472 12277 5422 20837 8419 34639 40506 20199 19187 1450 43543 12891 20696 31711 39801 7773 33559 9591 36649 14553 40633 12880 29190 10745 29247 72 42882 33691 36891 42193 16933 7813 35865 3168 2123 24249 32935 12646 40649 33682 2890 4229 36433 26445 13050...
output:
314
result:
ok "314"
Test #86:
score: 0
Accepted
time: 34ms
memory: 4248kb
input:
2126 29 658 721 381 636 145 591 1459 116 96 1329 2033 626 862 1798 1357 1727 271 134 922 1184 766 311 473 1017 1262 1978 1979 1188 1380 1827 548 1390 1011 1294 1939 1998 1465 686 499 1117 1003 301 996 225 212 1803 1213 1984 2086 1368 1081 1564 919 1637 223 39 2036 1977 1095 680 1194 1069 2121 1099 1...
output:
268
result:
ok "268"
Test #87:
score: 0
Accepted
time: 22ms
memory: 4656kb
input:
13676 3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...
output:
13676
result:
ok "13676"
Test #88:
score: 0
Accepted
time: 60ms
memory: 6752kb
input:
46494 2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...
output:
46494
result:
ok "46494"
Test #89:
score: 0
Accepted
time: 258ms
memory: 7772kb
input:
49818 7 49817 49818 49816 33052 5536 1092 2927 39341 49756 20060 43582 5595 34923 9128 37275 38020 1153 922 14357 26889 26308 37379 3054 32758 3448 11325 13065 41169 2116 41852 13850 27942 29862 21585 17451 48614 21670 6831 12797 37509 15023 21239 5707 44759 41572 33199 24931 23651 22500 23226 8649 ...
output:
145
result:
ok "145"
Test #90:
score: 0
Accepted
time: 854ms
memory: 10996kb
input:
49282 24 49281 49282 49280 5587 36390 3923 46396 37114 4310 44718 8153 15792 15463 18103 2420 23372 33221 43247 2062 43570 13826 2843 27706 27597 5489 23952 38834 4059 43794 157 45228 44959 24269 21678 32915 44913 21011 35638 26242 30095 36907 16885 33890 39272 27565 20580 25219 30411 26601 40083 32...
output:
413
result:
ok "413"
Subtask #6:
score: 0
Time Limit Exceeded
Dependency #2:
100%
Accepted
Dependency #5:
100%
Accepted
Test #91:
score: 20
Accepted
time: 282ms
memory: 7756kb
input:
48545 8 13498 42489 26830 26915 4714 38759 28009 9621 27595 8069 31935 13674 6728 3198 5508 37974 5372 36129 34433 22443 42244 27355 29611 9156 38806 18505 37889 7165 38932 6445 10334 12156 6173 13445 47054 42715 32099 26656 44414 37151 45966 21782 14480 29772 16610 46275 24790 14850 11899 17390 758...
output:
153
result:
ok "153"
Test #92:
score: 0
Accepted
time: 620ms
memory: 27280kb
input:
368741 2 6747 137488 187527 169657 212594 6 226823 56409 9 242612 339738 12 353304 14 179943 16 119809 204316 19 219812 293837 174747 336748 24 25 365013 125653 215395 29 30 348908 32 33 330591 138195 17271 37 86997 318755 96997 96633 3357 43 220612 76403 18522 47 48 311590 50 51 52 85398 180909 499...
output:
829
result:
ok "829"
Test #93:
score: 0
Accepted
time: 19ms
memory: 5912kb
input:
298523 1 92001 10609 3 263080 82597 6 7 8 9 288733 219502 53922 250568 169516 15 22305 17 18 19 20 32300 62621 23 251491 261937 280622 171399 28 33611 208337 49541 185551 175390 34 106155 36 37 197752 85174 94659 204540 270568 142747 127219 197476 28197 47 127985 160867 50 60482 255536 49534 215727 ...
output:
415
result:
ok "415"
Test #94:
score: -20
Time Limit Exceeded
input:
367797 13 145245 2 359420 111257 5 358051 165513 8 283077 94388 11 4758 223865 14 15 16 260678 116582 27202 20 269757 22 23 172014 242692 26 27 56415 196281 363808 84657 32 33 34 20822 36 37 240502 39 40 41 42 43 44 45 46 47 332027 81174 50 188326 52 53 54 55 56 57 58 115502 143731 61 48903 63 64 65...