QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #743914 | #5035. foo~ | dyj133446 | 30 | 151ms | 424100kb | C++14 | 1.5kb | 2024-11-13 20:17:59 | 2024-11-13 20:17:59 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=6e5+5,K=35;
int n,k,p[N],a[N],dp[N][K],f[N][K],g[N][K],pf[N][K],pg[N][K],ans,zhan[N],top,pre[N],suf[N];
void solve()
{
top=0;
for(int i=1;i<=n;i++)
{
while(top&&a[i]>a[zhan[top]])top--;
pre[i]=zhan[top];zhan[++top]=i;
}
top=0;
for(int i=n;i;i--)
{
while(top&&a[i]>a[zhan[top]])top--;
suf[i]=zhan[top];zhan[++top]=i;
}
memset(dp,-0x3f,sizeof(dp)),memset(f,-0x3f,sizeof(f)),memset(g,-0x3f,sizeof(g));
memset(pf,-0x3f,sizeof(pf)),memset(pg,-0x3f,sizeof(pg));
dp[1][0]=f[1][0]=g[1][0]=pf[1][0]=pg[1][0]=1;
for(int i=2;i<=n;i++)
{
for(int j=0;j<=k;j++)if(pre[i])
{
f[i][j]=max(f[i][j],f[pre[i]][j]+1);
pg[i][j]=max(pg[i][j],pg[pre[i]][j]);
pg[i][j]=max(pg[i][j],g[pre[i]][j]);
}
for(int j=1;j<=k;j++)
{
dp[i][j]=max({f[i][j-1],g[i][j-1],pf[i][j-1],pg[i][j-1]});
pf[i+1][j]=max(pf[i+1][j],dp[i][j]+1);
f[i+1][j]=max(f[i+1][j],dp[i][j]+1);
pg[i+1][j]=max(pg[i+1][j],dp[i][j]+1);
g[i+1][j]=max(g[i+1][j],dp[i][j]+1);
}
for(int j=0;j<=k;j++)if(suf[i])
{
pf[suf[i]][j]=max(pf[suf[i]][j],pf[i][j]);
f[suf[i]][j]=max(f[suf[i]][j],pf[i][j]);
g[suf[i]][j]=max(g[suf[i]][j],g[i][j]+1);
}
}
for(int i=1;i<=n;i++)ans=max(ans,dp[i][k]);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>p[i];
for(int i=1;i<=n;i++)if(p[i]==n)
{
for(int j=1;j<=n;j++)a[j]=p[(j+i-2)%n+1];
break;
}
solve(),reverse(a+2,a+n+1),solve();
cout<<ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 10
Accepted
time: 52ms
memory: 421792kb
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: 10
Accepted
time: 51ms
memory: 420528kb
input:
13 6 13 9 3 4 12 6 5 1 8 10 11 7 2
output:
13
result:
ok "13"
Test #3:
score: 10
Accepted
time: 52ms
memory: 421552kb
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: 10
Accepted
time: 40ms
memory: 421388kb
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: 10
Accepted
time: 40ms
memory: 421224kb
input:
13 2 1 4 2 3 5 6 7 8 9 10 12 11 13
output:
12
result:
ok "12"
Test #6:
score: 10
Accepted
time: 44ms
memory: 420888kb
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: 10
Accepted
time: 35ms
memory: 420408kb
input:
8 2 1 2 5 6 3 4 7 8
output:
8
result:
ok "8"
Test #8:
score: 10
Accepted
time: 52ms
memory: 421884kb
input:
11 5 3 11 2 10 6 5 1 4 8 7 9
output:
11
result:
ok "11"
Test #9:
score: 10
Accepted
time: 39ms
memory: 420148kb
input:
10 1 5 3 4 1 10 8 9 6 7 2
output:
6
result:
ok "6"
Test #10:
score: 10
Accepted
time: 36ms
memory: 420892kb
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: 10
Accepted
time: 53ms
memory: 421560kb
input:
6 3 4 1 5 6 2 3
output:
6
result:
ok "6"
Test #12:
score: 0
Wrong Answer
time: 51ms
memory: 419948kb
input:
1 1 1
output:
0
result:
wrong answer 1st words differ - expected: '1', found: '0'
Subtask #2:
score: 10
Accepted
Test #21:
score: 10
Accepted
time: 53ms
memory: 421944kb
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: 10
Accepted
time: 67ms
memory: 422120kb
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: 10
Accepted
time: 117ms
memory: 423932kb
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: 10
Accepted
time: 151ms
memory: 423092kb
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: 10
Accepted
time: 83ms
memory: 423576kb
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: 10
Accepted
time: 60ms
memory: 423432kb
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: 10
Accepted
time: 43ms
memory: 421540kb
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: 10
Accepted
time: 95ms
memory: 423760kb
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: 10
Accepted
time: 73ms
memory: 423416kb
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: 10
Accepted
time: 51ms
memory: 422924kb
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: 10
Accepted
time: 146ms
memory: 423364kb
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: 10
Accepted
time: 67ms
memory: 424100kb
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: 10
Accepted
time: 60ms
memory: 423068kb
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: 10
Accepted
time: 43ms
memory: 421388kb
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: 10
Accepted
time: 67ms
memory: 422680kb
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: 31ms
memory: 421664kb
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: 20
Accepted
time: 51ms
memory: 420624kb
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: 20
Accepted
time: 59ms
memory: 420964kb
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: 20
Accepted
time: 36ms
memory: 421488kb
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: 20
Accepted
time: 39ms
memory: 420220kb
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: 20
Accepted
time: 41ms
memory: 421620kb
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: 20
Accepted
time: 35ms
memory: 420080kb
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: 20
Accepted
time: 43ms
memory: 421788kb
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: 20
Accepted
time: 44ms
memory: 421332kb
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: 20
Accepted
time: 35ms
memory: 420740kb
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: 20
Accepted
time: 47ms
memory: 420368kb
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: 20
Accepted
time: 39ms
memory: 420012kb
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: 20
Accepted
time: 56ms
memory: 420772kb
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: 20
Accepted
time: 44ms
memory: 420888kb
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: 20
Accepted
time: 39ms
memory: 421332kb
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: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #2:
100%
Accepted
Dependency #5:
0%