QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#766942 | #8268. Tycho | _8_8_ | 5 | 3ms | 3732kb | C++20 | 1014b | 2024-11-20 19:22:51 | 2024-11-20 19:22:55 |
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = (int)1e3 + 12;
const ll inf = (ll)1e18;
ll b, p, d, n, a[N], dp[N], t[N];
ll get(ll l, ll r) {
return r / p - (l - 1) / p;
}
ll nx(ll f) {
return (f + p - 1) / p * p;
}
void test() {
cin >> b >> p >> d >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
a[++n] = b;
for(int i = 1; i <= n; i++) {
dp[i] = inf;
for(int j = i - 1; j >= 0; j--) {
ll v = dp[j] + (a[i] - a[j]) + get(nx(t[j]) + 1, nx(t[j]) + a[i] - a[j] - 1) * d + nx(t[j]) - t[j];
if(v < dp[i]) {
dp[i] = v;
t[i] = nx(t[j]) + (a[i] - a[j]);
}
}
// cout << i << ' ' << t[i] << ' ' << dp[i] << '\n';
}
cout << dp[n] << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// cin >> t;
while(t--)
test();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3592kb
input:
1000000000000 1 1000000 0
output:
1000000000000000000
result:
wrong answer 1st lines differ - expected: '1000000999999000000', found: '1000000000000000000'
Subtask #2:
score: 5
Accepted
Test #11:
score: 5
Accepted
time: 0ms
memory: 3720kb
input:
108 100 10000 5 10 20 30 40 98
output:
110
result:
ok single line: '110'
Test #12:
score: 5
Accepted
time: 0ms
memory: 3660kb
input:
118 100 10000 5 10 20 30 98 108
output:
120
result:
ok single line: '120'
Test #13:
score: 5
Accepted
time: 0ms
memory: 3716kb
input:
206 100 10000 5 10 20 30 98 196
output:
210
result:
ok single line: '210'
Test #14:
score: 5
Accepted
time: 0ms
memory: 3600kb
input:
128 100 10000 5 10 20 98 108 118
output:
130
result:
ok single line: '130'
Test #15:
score: 5
Accepted
time: 0ms
memory: 3660kb
input:
206 100 10000 5 10 20 98 108 196
output:
210
result:
ok single line: '210'
Test #16:
score: 5
Accepted
time: 0ms
memory: 3660kb
input:
216 100 10000 5 10 20 98 196 206
output:
220
result:
ok single line: '220'
Test #17:
score: 5
Accepted
time: 0ms
memory: 3676kb
input:
304 100 10000 5 10 20 98 196 294
output:
310
result:
ok single line: '310'
Test #18:
score: 5
Accepted
time: 0ms
memory: 3688kb
input:
138 100 10000 5 10 98 108 118 128
output:
140
result:
ok single line: '140'
Test #19:
score: 5
Accepted
time: 0ms
memory: 3648kb
input:
206 100 10000 5 10 98 108 118 196
output:
210
result:
ok single line: '210'
Test #20:
score: 5
Accepted
time: 0ms
memory: 3600kb
input:
216 100 10000 5 10 98 108 196 206
output:
220
result:
ok single line: '220'
Test #21:
score: 5
Accepted
time: 0ms
memory: 3596kb
input:
304 100 10000 5 10 98 108 196 294
output:
310
result:
ok single line: '310'
Test #22:
score: 5
Accepted
time: 0ms
memory: 3716kb
input:
226 100 10000 5 10 98 196 206 216
output:
230
result:
ok single line: '230'
Test #23:
score: 5
Accepted
time: 0ms
memory: 3680kb
input:
304 100 10000 5 10 98 196 206 294
output:
310
result:
ok single line: '310'
Test #24:
score: 5
Accepted
time: 0ms
memory: 3652kb
input:
314 100 10000 5 10 98 196 294 304
output:
320
result:
ok single line: '320'
Test #25:
score: 5
Accepted
time: 0ms
memory: 3716kb
input:
402 100 10000 5 10 98 196 294 392
output:
410
result:
ok single line: '410'
Test #26:
score: 5
Accepted
time: 0ms
memory: 3592kb
input:
148 100 10000 5 98 108 118 128 138
output:
150
result:
ok single line: '150'
Test #27:
score: 5
Accepted
time: 0ms
memory: 3732kb
input:
206 100 10000 5 98 108 118 128 196
output:
210
result:
ok single line: '210'
Test #28:
score: 5
Accepted
time: 0ms
memory: 3680kb
input:
216 100 10000 5 98 108 118 196 206
output:
220
result:
ok single line: '220'
Test #29:
score: 5
Accepted
time: 0ms
memory: 3676kb
input:
304 100 10000 5 98 108 118 196 294
output:
310
result:
ok single line: '310'
Test #30:
score: 5
Accepted
time: 0ms
memory: 3660kb
input:
226 100 10000 5 98 108 196 206 216
output:
230
result:
ok single line: '230'
Test #31:
score: 5
Accepted
time: 0ms
memory: 3596kb
input:
304 100 10000 5 98 108 196 206 294
output:
310
result:
ok single line: '310'
Test #32:
score: 5
Accepted
time: 0ms
memory: 3660kb
input:
314 100 10000 5 98 108 196 294 304
output:
320
result:
ok single line: '320'
Test #33:
score: 5
Accepted
time: 0ms
memory: 3632kb
input:
402 100 10000 5 98 108 196 294 392
output:
410
result:
ok single line: '410'
Test #34:
score: 5
Accepted
time: 0ms
memory: 3664kb
input:
236 100 10000 5 98 196 206 216 226
output:
240
result:
ok single line: '240'
Test #35:
score: 5
Accepted
time: 0ms
memory: 3596kb
input:
304 100 10000 5 98 196 206 216 294
output:
310
result:
ok single line: '310'
Test #36:
score: 5
Accepted
time: 0ms
memory: 3652kb
input:
314 100 10000 5 98 196 206 294 304
output:
320
result:
ok single line: '320'
Test #37:
score: 5
Accepted
time: 0ms
memory: 3660kb
input:
402 100 10000 5 98 196 206 294 392
output:
410
result:
ok single line: '410'
Test #38:
score: 5
Accepted
time: 0ms
memory: 3724kb
input:
324 100 10000 5 98 196 294 304 314
output:
330
result:
ok single line: '330'
Test #39:
score: 5
Accepted
time: 0ms
memory: 3720kb
input:
402 100 10000 5 98 196 294 304 392
output:
410
result:
ok single line: '410'
Test #40:
score: 5
Accepted
time: 0ms
memory: 3604kb
input:
412 100 10000 5 98 196 294 392 402
output:
420
result:
ok single line: '420'
Test #41:
score: 5
Accepted
time: 0ms
memory: 3660kb
input:
500 100 10000 5 98 196 294 392 490
output:
510
result:
ok single line: '510'
Test #42:
score: 5
Accepted
time: 0ms
memory: 3588kb
input:
10 2 10 2 1 3
output:
41
result:
ok single line: '41'
Test #43:
score: 5
Accepted
time: 0ms
memory: 3660kb
input:
100 21 10 2 5 54
output:
140
result:
ok single line: '140'
Test #44:
score: 5
Accepted
time: 0ms
memory: 3672kb
input:
100 21 10 9 18 21 53 62 85 86 88 90 91
output:
121
result:
ok single line: '121'
Test #45:
score: 5
Accepted
time: 0ms
memory: 3680kb
input:
100 21 10 10 30 39 40 43 45 49 52 57 70 72
output:
132
result:
ok single line: '132'
Test #46:
score: 5
Accepted
time: 0ms
memory: 3660kb
input:
156 20 1 10 19 37 54 70 85 99 112 124 135 145
output:
162
result:
ok single line: '162'
Test #47:
score: 5
Accepted
time: 0ms
memory: 3684kb
input:
156 20 20 10 19 37 54 70 85 99 112 124 135 145
output:
211
result:
ok single line: '211'
Test #48:
score: 5
Accepted
time: 0ms
memory: 3672kb
input:
156 20 30 10 19 37 54 70 85 99 112 124 135 145
output:
211
result:
ok single line: '211'
Test #49:
score: 5
Accepted
time: 0ms
memory: 3680kb
input:
18 4 5 2 8 15
output:
29
result:
ok single line: '29'
Test #50:
score: 5
Accepted
time: 0ms
memory: 3600kb
input:
18 4 0 2 8 15
output:
18
result:
ok single line: '18'
Test #51:
score: 5
Accepted
time: 0ms
memory: 3600kb
input:
18 10 100 2 8 15
output:
20
result:
ok single line: '20'
Test #52:
score: 5
Accepted
time: 0ms
memory: 3732kb
input:
18 4 100 0
output:
418
result:
ok single line: '418'
Test #53:
score: 5
Accepted
time: 0ms
memory: 3600kb
input:
65 20 100 3 14 25 33
output:
172
result:
ok single line: '172'
Subtask #3:
score: 0
Wrong Answer
Dependency #2:
100%
Accepted
Test #54:
score: 7
Accepted
time: 0ms
memory: 3604kb
input:
108 100 10000 5 10 20 30 40 98
output:
110
result:
ok single line: '110'
Test #55:
score: 7
Accepted
time: 0ms
memory: 3592kb
input:
118 100 10000 5 10 20 30 98 108
output:
120
result:
ok single line: '120'
Test #56:
score: 7
Accepted
time: 0ms
memory: 3600kb
input:
206 100 10000 5 10 20 30 98 196
output:
210
result:
ok single line: '210'
Test #57:
score: 7
Accepted
time: 0ms
memory: 3676kb
input:
128 100 10000 5 10 20 98 108 118
output:
130
result:
ok single line: '130'
Test #58:
score: 7
Accepted
time: 0ms
memory: 3724kb
input:
206 100 10000 5 10 20 98 108 196
output:
210
result:
ok single line: '210'
Test #59:
score: 7
Accepted
time: 0ms
memory: 3628kb
input:
216 100 10000 5 10 20 98 196 206
output:
220
result:
ok single line: '220'
Test #60:
score: 7
Accepted
time: 0ms
memory: 3656kb
input:
304 100 10000 5 10 20 98 196 294
output:
310
result:
ok single line: '310'
Test #61:
score: 7
Accepted
time: 0ms
memory: 3604kb
input:
138 100 10000 5 10 98 108 118 128
output:
140
result:
ok single line: '140'
Test #62:
score: 7
Accepted
time: 0ms
memory: 3688kb
input:
206 100 10000 5 10 98 108 118 196
output:
210
result:
ok single line: '210'
Test #63:
score: 7
Accepted
time: 0ms
memory: 3676kb
input:
216 100 10000 5 10 98 108 196 206
output:
220
result:
ok single line: '220'
Test #64:
score: 7
Accepted
time: 0ms
memory: 3720kb
input:
304 100 10000 5 10 98 108 196 294
output:
310
result:
ok single line: '310'
Test #65:
score: 7
Accepted
time: 0ms
memory: 3656kb
input:
226 100 10000 5 10 98 196 206 216
output:
230
result:
ok single line: '230'
Test #66:
score: 7
Accepted
time: 0ms
memory: 3656kb
input:
304 100 10000 5 10 98 196 206 294
output:
310
result:
ok single line: '310'
Test #67:
score: 7
Accepted
time: 0ms
memory: 3684kb
input:
314 100 10000 5 10 98 196 294 304
output:
320
result:
ok single line: '320'
Test #68:
score: 7
Accepted
time: 0ms
memory: 3660kb
input:
402 100 10000 5 10 98 196 294 392
output:
410
result:
ok single line: '410'
Test #69:
score: 7
Accepted
time: 0ms
memory: 3600kb
input:
148 100 10000 5 98 108 118 128 138
output:
150
result:
ok single line: '150'
Test #70:
score: 7
Accepted
time: 0ms
memory: 3648kb
input:
206 100 10000 5 98 108 118 128 196
output:
210
result:
ok single line: '210'
Test #71:
score: 7
Accepted
time: 0ms
memory: 3588kb
input:
216 100 10000 5 98 108 118 196 206
output:
220
result:
ok single line: '220'
Test #72:
score: 7
Accepted
time: 0ms
memory: 3656kb
input:
304 100 10000 5 98 108 118 196 294
output:
310
result:
ok single line: '310'
Test #73:
score: 7
Accepted
time: 0ms
memory: 3644kb
input:
226 100 10000 5 98 108 196 206 216
output:
230
result:
ok single line: '230'
Test #74:
score: 7
Accepted
time: 0ms
memory: 3664kb
input:
304 100 10000 5 98 108 196 206 294
output:
310
result:
ok single line: '310'
Test #75:
score: 7
Accepted
time: 0ms
memory: 3680kb
input:
314 100 10000 5 98 108 196 294 304
output:
320
result:
ok single line: '320'
Test #76:
score: 7
Accepted
time: 0ms
memory: 3656kb
input:
402 100 10000 5 98 108 196 294 392
output:
410
result:
ok single line: '410'
Test #77:
score: 7
Accepted
time: 0ms
memory: 3676kb
input:
236 100 10000 5 98 196 206 216 226
output:
240
result:
ok single line: '240'
Test #78:
score: 7
Accepted
time: 0ms
memory: 3732kb
input:
304 100 10000 5 98 196 206 216 294
output:
310
result:
ok single line: '310'
Test #79:
score: 7
Accepted
time: 0ms
memory: 3644kb
input:
314 100 10000 5 98 196 206 294 304
output:
320
result:
ok single line: '320'
Test #80:
score: 7
Accepted
time: 0ms
memory: 3724kb
input:
402 100 10000 5 98 196 206 294 392
output:
410
result:
ok single line: '410'
Test #81:
score: 7
Accepted
time: 0ms
memory: 3604kb
input:
324 100 10000 5 98 196 294 304 314
output:
330
result:
ok single line: '330'
Test #82:
score: 7
Accepted
time: 0ms
memory: 3676kb
input:
402 100 10000 5 98 196 294 304 392
output:
410
result:
ok single line: '410'
Test #83:
score: 7
Accepted
time: 0ms
memory: 3684kb
input:
412 100 10000 5 98 196 294 392 402
output:
420
result:
ok single line: '420'
Test #84:
score: 7
Accepted
time: 0ms
memory: 3600kb
input:
500 100 10000 5 98 196 294 392 490
output:
510
result:
ok single line: '510'
Test #85:
score: 7
Accepted
time: 0ms
memory: 3716kb
input:
10 2 10 2 1 3
output:
41
result:
ok single line: '41'
Test #86:
score: 7
Accepted
time: 0ms
memory: 3728kb
input:
100 21 10 2 5 54
output:
140
result:
ok single line: '140'
Test #87:
score: 7
Accepted
time: 0ms
memory: 3660kb
input:
100 21 10 9 18 21 53 62 85 86 88 90 91
output:
121
result:
ok single line: '121'
Test #88:
score: 7
Accepted
time: 0ms
memory: 3672kb
input:
100 21 10 10 30 39 40 43 45 49 52 57 70 72
output:
132
result:
ok single line: '132'
Test #89:
score: 7
Accepted
time: 0ms
memory: 3600kb
input:
156 20 1 10 19 37 54 70 85 99 112 124 135 145
output:
162
result:
ok single line: '162'
Test #90:
score: 7
Accepted
time: 0ms
memory: 3720kb
input:
156 20 20 10 19 37 54 70 85 99 112 124 135 145
output:
211
result:
ok single line: '211'
Test #91:
score: 7
Accepted
time: 0ms
memory: 3652kb
input:
156 20 30 10 19 37 54 70 85 99 112 124 135 145
output:
211
result:
ok single line: '211'
Test #92:
score: 7
Accepted
time: 0ms
memory: 3580kb
input:
10 2 10 0
output:
50
result:
ok single line: '50'
Test #93:
score: 7
Accepted
time: 0ms
memory: 3664kb
input:
10 2 10 9 1 2 3 4 5 6 7 8 9
output:
10
result:
ok single line: '10'
Test #94:
score: 7
Accepted
time: 0ms
memory: 3724kb
input:
10 2 10 3 2 4 6
output:
20
result:
ok single line: '20'
Test #95:
score: 7
Accepted
time: 0ms
memory: 3728kb
input:
100 2 10 33 2 5 6 9 10 12 18 26 29 30 32 34 35 42 49 50 52 53 55 56 58 61 62 63 69 71 73 74 82 89 91 93 94
output:
356
result:
ok single line: '356'
Test #96:
score: 7
Accepted
time: 0ms
memory: 3664kb
input:
100 2 10 50 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
output:
340
result:
ok single line: '340'
Test #97:
score: 7
Accepted
time: 0ms
memory: 3588kb
input:
100 2 10 50 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
output:
340
result:
ok single line: '340'
Test #98:
score: 7
Accepted
time: 0ms
memory: 3604kb
input:
100 2 10 50 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
output:
101
result:
ok single line: '101'
Test #99:
score: 7
Accepted
time: 3ms
memory: 3612kb
input:
1000 2 10 999 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 9...
output:
1000
result:
ok single line: '1000'
Test #100:
score: 0
Wrong Answer
time: 0ms
memory: 3664kb
input:
1000 42 15 100 9 10 31 35 39 42 53 68 75 77 78 92 117 121 123 141 146 147 157 166 167 193 221 222 231 247 255 265 275 292 305 313 341 343 344 352 357 364 371 380 388 392 410 417 418 445 450 451 452 460 476 479 485 498 501 505 515 524 532 539 542 565 569 570 580 581 585 593 607 618 633 634 642 661 66...
output:
1132
result:
wrong answer 1st lines differ - expected: '1126', found: '1132'
Subtask #4:
score: 0
Wrong Answer
Test #109:
score: 0
Wrong Answer
time: 0ms
memory: 3620kb
input:
1000000000000 1 1000000 0
output:
1000000000000000000
result:
wrong answer 1st lines differ - expected: '1000000999999000000', found: '1000000000000000000'
Subtask #5:
score: 0
Wrong Answer
Dependency #2:
100%
Accepted
Test #179:
score: 0
Wrong Answer
time: 0ms
memory: 3596kb
input:
1000000000000 1 1000000 0
output:
1000000000000000000
result:
wrong answer 1st lines differ - expected: '1000000999999000000', found: '1000000000000000000'
Subtask #6:
score: 0
Skipped
Dependency #1:
0%
Subtask #7:
score: 0
Skipped
Dependency #1:
0%