QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #307158 | #2500. Collecting Stamps 3 | OAleksa | 15 | 5ms | 4716kb | C++14 | 2.4kb | 2024-01-18 06:11:58 | 2024-01-18 06:11:59 |
Judging History
answer
#include <bits/stdc++.h>
//ako ovaj vaso daso misli da me pobedjuje.....
using namespace std;
#define int long long
#define f first
#define s second
const int N = 210;
const int inf = 1e18;
int n, l, x[N], t[N], dp[N][N][2][2];
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tt = 1;
//cin >> tt;
while (tt--) {
cin >> n >> l;
for (int i = 1;i <= n;i++) {
cin >> x[i];
}
for (int i = 1;i <= n;i++) {
cin >> t[i];
}
x[n + 1] = l;
for (int i = 0;i <= n;i++) {
for (int j = 0;j <= n;j++)
dp[i][j][0][0] = dp[i][j][1][0] = inf;
}
//3-i/j
//4-time/skor
dp[0][0][0][0] = dp[0][0][1][0] = 0;
int ans = 0;
for (int i = 0;i <= n;i++) {
for (int j = 0;j <= n;j++) {
if (i + j > n)
break;
for (int k = i - 1;k >= 0;k--) {
int time = dp[k][j][0][0] + abs(x[i] - x[k]);
if (dp[i][j][0][1] < dp[k][j][0][1] + (time <= t[i])) {
dp[i][j][0][1] = dp[k][j][0][1] + (time <= t[i]);
dp[i][j][0][0] = time;
}
else if (dp[i][j][0][1] == dp[k][j][0][1] + (time <= t[i]))
dp[i][j][0][0] = min(dp[i][j][0][0], time);
time = dp[k][j][1][0] + x[i] + (l - x[n - j + 1]);
if (dp[i][j][0][1] < dp[k][j][1][1] + (time <= t[i])) {
dp[i][j][0][1] = dp[k][j][1][1] + (time <= t[i]);
dp[i][j][0][0] = time;
}
else if (dp[i][j][0][1] == dp[k][j][1][1] + (time <= t[i]))
dp[i][j][0][0] = min(dp[i][j][0][0], time);
}
for (int k = j - 1;k >= 0;k--) {
int time = dp[i][k][1][0] + abs(x[n - j + 1] - x[n - k + 1]);
if (dp[i][j][1][1] < dp[i][k][1][1] + (time <= t[n - j + 1])) {
dp[i][j][1][1] = dp[i][k][1][1] + (time <= t[n - j + 1]);
dp[i][j][1][0] = time;
}
else if (dp[i][j][1][1] == dp[i][k][1][1] + (time <= t[n - j + 1]))
dp[i][j][1][0] = min(dp[i][j][1][0], time);
time = dp[i][k][0][0] + x[i] + (l - x[n - j + 1]);
if (dp[i][j][1][1] <= dp[i][k][0][1] + (time <= t[n - j + 1])) {
dp[i][j][1][1] = dp[i][k][0][1] + (time <= t[n - j + 1]);
dp[i][j][1][0] = min(dp[i][j][1][0], time);
}
}
if (i == 0 && j > 0)
dp[i][j][0][0] = 2 * (l - x[n - j + 1]);
if (j == 0 && i > 0)
dp[i][j][1][0] = 2 * x[i];
ans = max(ans, max(dp[i][j][0][1], dp[i][j][1][1]));
}
}
cout << ans;
}
return 0;
}
詳細信息
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 0ms
memory: 3512kb
input:
5 180 137 149 164 167 171 18 76 14 55 116
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3504kb
input:
5 198 5 12 18 190 192 16 43 200 33 0
output:
4
result:
ok single line: '4'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
9 198 3 17 22 33 43 44 48 54 65 0 17 29 32 38 46 45 54 66
output:
5
result:
ok single line: '5'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3568kb
input:
6 171 22 30 46 85 96 149 18 179 19 69 87 96
output:
3
result:
ok single line: '3'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
7 198 5 8 14 188 191 194 197 7 18 50 69 80 35 8
output:
7
result:
ok single line: '7'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
12 198 71 72 83 94 108 112 119 140 142 143 166 174 124 119 124 111 91 94 85 48 60 63 40 32
output:
9
result:
ok single line: '9'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
8 178 32 55 69 99 115 134 152 156 61 109 37 65 76 31 103 0
output:
2
result:
ok single line: '2'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
10 198 1 2 3 10 14 182 183 190 192 196 0 3 17 46 115 142 79 44 8 1
output:
7
result:
ok single line: '7'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
12 198 18 23 45 53 54 70 101 103 105 110 118 152 21 24 49 45 61 78 108 111 97 107 122 144
output:
8
result:
ok single line: '8'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
1 2 1 0
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 1ms
memory: 3684kb
input:
1 2 1 1
output:
1
result:
ok single line: '1'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
12 170 1 4 7 28 32 63 84 85 90 94 96 107 116 77 30 93 134 99 190 103 96 189 173 191
output:
12
result:
ok single line: '12'
Test #13:
score: 0
Accepted
time: 1ms
memory: 3592kb
input:
12 200 14 25 35 57 113 120 141 143 146 153 173 179 126 137 127 141 135 134 122 100 164 185 163 188
output:
9
result:
ok single line: '9'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
7 171 4 31 65 82 125 128 150 1 24 51 55 8 23 18
output:
0
result:
ok single line: '0'
Test #15:
score: 0
Accepted
time: 1ms
memory: 3652kb
input:
8 175 28 41 67 77 89 104 106 138 16 9 0 56 25 39 42 14
output:
0
result:
ok single line: '0'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3728kb
input:
12 13 1 2 3 4 5 6 7 8 9 10 11 12 0 200 200 200 200 200 200 200 200 200 200 200
output:
11
result:
ok single line: '11'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
12 13 1 2 3 4 5 6 7 8 9 10 11 12 200 200 200 200 200 200 200 200 200 200 200 200
output:
12
result:
ok single line: '12'
Subtask #2:
score: 10
Accepted
Dependency #1:
100%
Accepted
Test #18:
score: 10
Accepted
time: 0ms
memory: 3648kb
input:
14 995216877 1547993 21872568 117017367 130195631 172395048 303811509 316432767 467657618 489836809 577455025 608824907 616559666 696830761 987994277 177587234 629350557 411262955 841625784 194076652 479115452 408683201 364268603 109991323 631975956 373092938 104263243 949468174 778758041
output:
10
result:
ok single line: '10'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
10 957307325 40526371 60810082 60820390 94278571 207413180 330699274 360357075 397321615 518571948 925010264 9046488 10048815 913320939 270546395 356388769 269607042 444929100 365070745 244210838 525063997
output:
5
result:
ok single line: '5'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
12 883313120 21829204 37314859 81878430 327591142 441913998 457602296 638182996 701569600 703036538 746679793 749878957 787945504 174062762 824574750 328610501 218823308 285317760 395266065 777626897 143435091 963710877 291722991 400725598 526884305
output:
7
result:
ok single line: '7'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
14 998374538 55005020 136253295 167840188 209817987 226142739 229002260 261542168 348671858 402488752 403736667 438697153 557394603 610401423 811914415 797134194 197645577 250510705 394957044 463870699 942748546 425910619 172208631 705492158 840453618 74694920 400759184 258764540 940515505
output:
10
result:
ok single line: '10'
Test #22:
score: 0
Accepted
time: 0ms
memory: 3520kb
input:
9 762152627 111917773 134919116 155422008 328301493 333796036 373204294 480675107 546940509 730594645 821492438 709486524 476358560 184207693 334323157 867541572 215296124 311813854 959010325
output:
6
result:
ok single line: '6'
Test #23:
score: 0
Accepted
time: 1ms
memory: 3652kb
input:
15 999999998 1924124 2952838 5239098 18421969 37271499 37853044 47082651 99300521 908208854 922862249 934908176 942743269 944533396 960738196 965737420 70449273 153849854 272974989 411149518 597026615 826426654 1000000000 1000000000 956070845 711435863 494663293 335470813 212269294 111635214 34262569
output:
14
result:
ok single line: '14'
Test #24:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
13 999999998 428180064 453825926 496177951 542265409 564354140 623999424 733991584 735577512 795234730 808832729 820421093 895605891 931423865 571819925 546174077 503822037 457734599 435645856 376000580 266008406 264422493 204765262 191167259 179578899 104394103 68576140
output:
5
result:
ok single line: '5'
Test #25:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
14 999999998 4515495 9904992 25475620 73563324 76637608 86769631 94216071 907247859 931656410 933666727 984350334 984974543 987268027 993426086 4515493 32083815 92928361 222018214 403518475 699592247 107133306 549366014 854705483 546489353 311231200 133429435 54720779 15604910
output:
12
result:
ok single line: '12'
Test #26:
score: 0
Accepted
time: 1ms
memory: 3728kb
input:
14 999999998 11313319 26979744 49935337 85404750 170975560 260885711 426294698 455696159 526506498 589306257 589663449 591771082 689721576 725376405 11313326 26979742 49935327 85404740 170975561 260885705 426294707 455696158 526506507 589306249 589663447 591771088 689721566 725376399
output:
7
result:
ok single line: '7'
Test #27:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
8 999999998 37723100 54496083 61229468 86267478 933661726 941061931 942456383 967540455 102642189 309948600 543550277 823723776 671118026 423382750 197908898 32459535
output:
7
result:
ok single line: '7'
Test #28:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
9 999999998 72636384 114113215 283235927 352065895 428412245 467023512 617585180 670550999 744184217 72636393 114113205 283235920 352065894 428412238 467023515 617585183 670550991 744184224
output:
4
result:
ok single line: '4'
Test #29:
score: 0
Accepted
time: 1ms
memory: 3656kb
input:
15 750000000 67849176 127883989 155065871 238001302 268263321 338797295 349803926 413688883 508345422 512345713 525681461 579549983 620335922 691434787 712230646 284918450 461047175 730144198 890540293 327480147 458250023 860792497 713796452 937154500 888159898 595960243 719523848 751461081 71933108...
output:
15
result:
ok single line: '15'
Test #30:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
15 1000000000 74228911 77263645 191730809 210720482 227897818 238710820 309590716 309987587 418571300 604252987 609022749 671850901 672628347 677322052 995213366 738778850 901756738 890749623 697851638 797959781 799410529 712105420 584272347 942330916 734598992 609756629 719271748 668479825 72328357...
output:
13
result:
ok single line: '13'
Test #31:
score: 0
Accepted
time: 1ms
memory: 3648kb
input:
14 895598008 66542840 99386933 110912372 219124550 312351782 414412857 640116276 686443224 739820207 778350188 782973215 800288780 816382833 837042060 42039832 39815432 76646262 209976603 60083683 325225551 194273248 36132227 96829464 5309136 94973134 80925626 57197891 35032333
output:
0
result:
ok single line: '0'
Test #32:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
13 999448786 9338040 37102715 150633853 231157464 282664177 315376219 316161980 551670190 623185571 869045820 901788332 970042192 980534405 3370325 8304384 35281948 199742422 241568836 302830252 6537739 280099730 314165160 87616629 7444573 6147628 14398310
output:
0
result:
ok single line: '0'
Test #33:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
15 10000 1 2 3 4 5 6 7 2000 8000 9994 9995 9996 9997 9998 9999 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 3999 3999 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
output:
14
result:
ok single line: '14'
Test #34:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
15 16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 5 100 100 100 100 100 100 100 100 100 6 100 100 100 5
output:
14
result:
ok single line: '14'
Test #35:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
15 16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 5 100 100 100 5 100 100 100 100 100 6 100 100 100 5
output:
13
result:
ok single line: '13'
Subtask #3:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Test #36:
score: 10
Accepted
time: 5ms
memory: 4716kb
input:
179 183 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 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 101...
output:
89
result:
ok single line: '89'
Test #37:
score: 0
Accepted
time: 3ms
memory: 4468kb
input:
139 170 1 2 3 4 5 6 7 8 10 11 12 13 14 15 16 17 18 19 20 21 23 24 25 26 27 29 30 31 32 33 35 36 37 38 39 40 42 45 46 48 49 50 52 53 54 55 56 58 60 61 62 64 65 66 67 68 70 71 72 74 76 79 80 82 83 85 86 87 88 89 90 91 92 93 94 95 96 97 98 100 101 102 103 104 107 109 110 111 112 113 114 115 116 117 119...
output:
88
result:
ok single line: '88'
Test #38:
score: 0
Accepted
time: 2ms
memory: 4212kb
input:
101 183 1 2 3 4 6 7 8 9 10 15 18 20 22 28 29 30 31 32 34 35 38 39 40 41 42 43 45 46 51 52 55 56 60 62 63 65 66 67 68 73 76 78 79 81 82 83 84 85 86 87 88 89 91 92 96 97 99 107 108 112 113 116 117 118 124 125 126 128 130 131 132 136 137 138 139 140 141 144 145 146 147 149 150 151 152 158 159 162 163 1...
output:
59
result:
ok single line: '59'
Test #39:
score: 0
Accepted
time: 3ms
memory: 4560kb
input:
135 176 1 2 3 4 5 6 7 8 9 10 11 12 14 15 16 17 18 20 21 22 23 25 26 27 30 31 32 34 35 37 38 39 40 41 42 43 44 46 47 48 50 51 52 53 54 55 56 57 58 59 61 62 63 65 66 68 69 71 72 73 74 75 76 78 80 81 82 83 84 85 86 87 88 90 91 92 93 95 97 99 101 102 103 104 105 106 108 110 111 112 114 116 117 121 122 1...
output:
80
result:
ok single line: '80'
Test #40:
score: 0
Accepted
time: 4ms
memory: 4632kb
input:
154 188 1 2 3 4 5 6 7 8 9 10 12 13 14 15 16 17 18 20 21 23 27 28 29 30 31 32 33 35 36 37 38 39 40 41 42 43 44 45 47 48 49 50 52 53 54 58 60 61 62 63 64 65 66 67 68 69 70 72 74 75 76 77 78 80 81 82 83 84 85 88 89 90 91 92 94 95 97 98 99 100 101 102 103 104 105 107 108 109 110 111 112 113 114 116 117 ...
output:
97
result:
ok single line: '97'
Test #41:
score: 0
Accepted
time: 0ms
memory: 4216kb
input:
93 198 1 2 3 4 5 6 7 8 9 10 11 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 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 ...
output:
91
result:
ok single line: '91'
Test #42:
score: 0
Accepted
time: 2ms
memory: 4216kb
input:
82 198 109 110 112 113 114 115 117 118 119 120 121 122 123 124 125 126 127 128 129 130 132 133 134 135 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 181 182 183 184 185 186 1...
output:
40
result:
ok single line: '40'
Test #43:
score: 0
Accepted
time: 1ms
memory: 4188kb
input:
92 198 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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 181 182 183 184 185 186 187 188 189 190 191 192 ...
output:
91
result:
ok single line: '91'
Test #44:
score: 0
Accepted
time: 1ms
memory: 3988kb
input:
56 198 75 76 77 80 84 85 86 89 90 92 94 99 102 108 109 110 113 115 117 119 120 123 124 128 130 131 134 136 138 145 147 149 151 152 160 162 163 165 166 167 168 169 173 174 179 180 181 182 183 185 186 189 192 194 195 197 132 121 126 108 108 112 109 99 110 105 96 106 92 91 98 97 80 84 82 81 82 76 78 76...
output:
30
result:
ok single line: '30'
Test #45:
score: 0
Accepted
time: 2ms
memory: 4172kb
input:
94 198 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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 178 179 180 181 182 183 184 185 186 187 188 189 190 1...
output:
93
result:
ok single line: '93'
Test #46:
score: 0
Accepted
time: 1ms
memory: 4044kb
input:
79 198 1 2 3 4 6 8 9 10 11 13 14 15 16 17 18 19 20 21 22 24 25 27 28 29 31 32 33 34 35 39 40 41 42 44 45 46 47 49 50 52 53 54 55 56 58 59 60 61 63 64 65 68 69 70 71 72 73 76 77 78 79 80 81 82 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 3 4 0 10 12 8 16 7 2 8 11 17 8 12 22 22 19 29 31 19 16 31 25 29...
output:
44
result:
ok single line: '44'
Test #47:
score: -10
Wrong Answer
time: 1ms
memory: 4204kb
input:
95 198 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 150 151 152 153 154 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 19...
output:
67
result:
wrong answer 1st lines differ - expected: '64', found: '67'
Subtask #4:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
0%