QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#711218	#8268. Tycho	makrav	12	3ms	3916kb	C++20	1.2kb	2024-11-05 03:16:43	2024-11-05 03:16:49

Judging History

你现在查看的是最新测评结果

[2024-11-05 03:16:49]
评测

测评结果：12
用时：3ms
内存：3916kb

查看

[2024-11-05 03:16:43]
提交

answer

#include <bits/stdc++.h>
#include <cassert>

using namespace std;
using ll = long long;

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define sc second
#define int ll

mt19937 rnd(time(NULL));
template<typename T>
void shuf(vector<T>& a) {
    for (int i = 1; i < sz(a); i++) swap(a[i], a[rnd() % (i + 1)]);
}

void solve() {
    int b, p, d, n; cin >> b >> p >> d >> n;
    vector<int> a(n + 2);
    for (int i = 1; i <= n; i++) cin >> a[i];
    a[n + 1] = b;
    
    vector<int> dp(n + 2, 0);
    for (int i = n; i >= 0; i--) {
        dp[i] = 1e18;
        for (int nxt = i + 1; nxt <= n + 1; nxt++) {
            int path = (a[nxt] - a[i] + p - 1) / p * p;
            if (nxt == n + 1) path = a[nxt] - a[i];
            int pts = (a[nxt] - a[i] - 1) / p;
            dp[i] = min(dp[i], dp[nxt] + path + pts * d);
        }
    }
    cout << dp[0] << '\n';
}

signed main() {
    int tt = 1;
    #ifdef LOCAL 
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        cin >> tt;
    #else
        ios::sync_with_stdio(false); 
        cin.tie(0); cout.tie(0);
    #endif

    while (tt--) {
        solve();
    }

    return 0;
}

源文件, 语言: C++20

详细

Subtask #1:

score: 0

Wrong Answer

Test #1:

score: 0

Wrong Answer

time: 1ms

memory: 3668kb

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: 3604kb

input:

108 100 10000 5
10
20
30
40
98

output:

result:

ok single line: '110'

Test #12:

score: 5

Accepted

time: 0ms

memory: 3604kb

input:

118 100 10000 5
10
20
30
98
108

output:

result:

ok single line: '120'

Test #13:

score: 5

Accepted

time: 0ms

memory: 3884kb

input:

206 100 10000 5
10
20
30
98
196

output:

result:

ok single line: '210'

Test #14:

score: 5

Accepted

time: 0ms

memory: 3556kb

input:

128 100 10000 5
10
20
98
108
118

output:

result:

ok single line: '130'

Test #15:

score: 5

Accepted

time: 0ms

memory: 3816kb

input:

206 100 10000 5
10
20
98
108
196

output:

result:

ok single line: '210'

Test #16:

score: 5

Accepted

time: 0ms

memory: 3556kb

input:

216 100 10000 5
10
20
98
196
206

output:

result:

ok single line: '220'

Test #17:

score: 5

Accepted

time: 0ms

memory: 3880kb

input:

304 100 10000 5
10
20
98
196
294

output:

result:

ok single line: '310'

Test #18:

score: 5

Accepted

time: 0ms

memory: 3656kb

input:

138 100 10000 5
10
98
108
118
128

output:

result:

ok single line: '140'

Test #19:

score: 5

Accepted

time: 0ms

memory: 3656kb

input:

206 100 10000 5
10
98
108
118
196

output:

result:

ok single line: '210'

Test #20:

score: 5

Accepted

time: 0ms

memory: 3656kb

input:

216 100 10000 5
10
98
108
196
206

output:

result:

ok single line: '220'

Test #21:

score: 5

Accepted

time: 0ms

memory: 3652kb

input:

304 100 10000 5
10
98
108
196
294

output:

result:

ok single line: '310'

Test #22:

score: 5

Accepted

time: 0ms

memory: 3888kb

input:

226 100 10000 5
10
98
196
206
216

output:

result:

ok single line: '230'

Test #23:

score: 5

Accepted

time: 0ms

memory: 3884kb

input:

304 100 10000 5
10
98
196
206
294

output:

result:

ok single line: '310'

Test #24:

score: 5

Accepted

time: 0ms

memory: 3644kb

input:

314 100 10000 5
10
98
196
294
304

output:

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:

result:

ok single line: '410'

Test #26:

score: 5

Accepted

time: 0ms

memory: 3908kb

input:

148 100 10000 5
98
108
118
128
138

output:

result:

ok single line: '150'

Test #27:

score: 5

Accepted

time: 0ms

memory: 3660kb

input:

206 100 10000 5
98
108
118
128
196

output:

result:

ok single line: '210'

Test #28:

score: 5

Accepted

time: 0ms

memory: 3656kb

input:

216 100 10000 5
98
108
118
196
206

output:

result:

ok single line: '220'

Test #29:

score: 5

Accepted

time: 0ms

memory: 3612kb

input:

304 100 10000 5
98
108
118
196
294

output:

result:

ok single line: '310'

Test #30:

score: 5

Accepted

time: 0ms

memory: 3604kb

input:

226 100 10000 5
98
108
196
206
216

output:

result:

ok single line: '230'

Test #31:

score: 5

Accepted

time: 0ms

memory: 3612kb

input:

304 100 10000 5
98
108
196
206
294

output:

result:

ok single line: '310'

Test #32:

score: 5

Accepted

time: 0ms

memory: 3604kb

input:

314 100 10000 5
98
108
196
294
304

output:

result:

ok single line: '320'

Test #33:

score: 5

Accepted

time: 0ms

memory: 3904kb

input:

402 100 10000 5
98
108
196
294
392

output:

result:

ok single line: '410'

Test #34:

score: 5

Accepted

time: 0ms

memory: 3904kb

input:

236 100 10000 5
98
196
206
216
226

output:

result:

ok single line: '240'

Test #35:

score: 5

Accepted

time: 0ms

memory: 3676kb

input:

304 100 10000 5
98
196
206
216
294

output:

result:

ok single line: '310'

Test #36:

score: 5

Accepted

time: 1ms

memory: 3812kb

input:

314 100 10000 5
98
196
206
294
304

output:

result:

ok single line: '320'

Test #37:

score: 5

Accepted

time: 0ms

memory: 3608kb

input:

402 100 10000 5
98
196
206
294
392

output:

result:

ok single line: '410'

Test #38:

score: 5

Accepted

time: 0ms

memory: 3876kb

input:

324 100 10000 5
98
196
294
304
314

output:

result:

ok single line: '330'

Test #39:

score: 5

Accepted

time: 0ms

memory: 3808kb

input:

402 100 10000 5
98
196
294
304
392

output:

result:

ok single line: '410'

Test #40:

score: 5

Accepted

time: 0ms

memory: 3680kb

input:

412 100 10000 5
98
196
294
392
402

output:

result:

ok single line: '420'

Test #41:

score: 5

Accepted

time: 0ms

memory: 3888kb

input:

500 100 10000 5
98
196
294
392
490

output:

result:

ok single line: '510'

Test #42:

score: 5

Accepted

time: 0ms

memory: 3660kb

input:

10 2 10 2
1
3

output:

result:

ok single line: '41'

Test #43:

score: 5

Accepted

time: 0ms

memory: 3876kb

input:

100 21 10 2
5
54

output:

result:

ok single line: '140'

Test #44:

score: 5

Accepted

time: 0ms

memory: 3600kb

input:

100 21 10 9
18
21
53
62
85
86
88
90
91

output:

result:

ok single line: '121'

Test #45:

score: 5

Accepted

time: 0ms

memory: 3672kb

input:

100 21 10 10
30
39
40
43
45
49
52
57
70
72

output:

result:

ok single line: '132'

Test #46:

score: 5

Accepted

time: 0ms

memory: 3604kb

input:

156 20 1 10
19
37
54
70
85
99
112
124
135
145

output:

result:

ok single line: '162'

Test #47:

score: 5

Accepted

time: 0ms

memory: 3660kb

input:

156 20 20 10
19
37
54
70
85
99
112
124
135
145

output:

result:

ok single line: '211'

Test #48:

score: 5

Accepted

time: 0ms

memory: 3892kb

input:

156 20 30 10
19
37
54
70
85
99
112
124
135
145

output:

result:

ok single line: '211'

Test #49:

score: 5

Accepted

time: 0ms

memory: 3912kb

input:

18 4 5 2
8
15

output:

result:

ok single line: '29'

Test #50:

score: 5

Accepted

time: 0ms

memory: 3884kb

input:

18 4 0 2
8
15

output:

result:

ok single line: '18'

Test #51:

score: 5

Accepted

time: 0ms

memory: 3612kb

input:

18 10 100 2
8
15

output:

result:

ok single line: '20'

Test #52:

score: 5

Accepted

time: 0ms

memory: 3652kb

input:

18 4 100 0

output:

result:

ok single line: '418'

Test #53:

score: 5

Accepted

time: 0ms

memory: 3880kb

input:

65 20 100 3
14
25
33

output:

result:

ok single line: '172'

Subtask #3:

score: 7

Accepted

Dependency #2:

100%

Accepted

Test #54:

score: 7

Accepted

time: 0ms

memory: 3656kb

input:

108 100 10000 5
10
20
30
40
98

output:

result:

ok single line: '110'

Test #55:

score: 7

Accepted

time: 0ms

memory: 3652kb

input:

118 100 10000 5
10
20
30
98
108

output:

result:

ok single line: '120'

Test #56:

score: 7

Accepted

time: 0ms

memory: 3660kb

input:

206 100 10000 5
10
20
30
98
196

output:

result:

ok single line: '210'

Test #57:

score: 7

Accepted

time: 0ms

memory: 3660kb

input:

128 100 10000 5
10
20
98
108
118

output:

result:

ok single line: '130'

Test #58:

score: 7

Accepted

time: 0ms

memory: 3680kb

input:

206 100 10000 5
10
20
98
108
196

output:

result:

ok single line: '210'

Test #59:

score: 7

Accepted

time: 0ms

memory: 3908kb

input:

216 100 10000 5
10
20
98
196
206

output:

result:

ok single line: '220'

Test #60:

score: 7

Accepted

time: 0ms

memory: 3888kb

input:

304 100 10000 5
10
20
98
196
294

output:

result:

ok single line: '310'

Test #61:

score: 7

Accepted

time: 0ms

memory: 3576kb

input:

138 100 10000 5
10
98
108
118
128

output:

result:

ok single line: '140'

Test #62:

score: 7

Accepted

time: 0ms

memory: 3608kb

input:

206 100 10000 5
10
98
108
118
196

output:

result:

ok single line: '210'

Test #63:

score: 7

Accepted

time: 0ms

memory: 3912kb

input:

216 100 10000 5
10
98
108
196
206

output:

result:

ok single line: '220'

Test #64:

score: 7

Accepted

time: 0ms

memory: 3680kb

input:

304 100 10000 5
10
98
108
196
294

output:

result:

ok single line: '310'

Test #65:

score: 7

Accepted

time: 1ms

memory: 3660kb

input:

226 100 10000 5
10
98
196
206
216

output:

result:

ok single line: '230'

Test #66:

score: 7

Accepted

time: 0ms

memory: 3652kb

input:

304 100 10000 5
10
98
196
206
294

output:

result:

ok single line: '310'

Test #67:

score: 7

Accepted

time: 0ms

memory: 3876kb

input:

314 100 10000 5
10
98
196
294
304

output:

result:

ok single line: '320'

Test #68:

score: 7

Accepted

time: 0ms

memory: 3656kb

input:

402 100 10000 5
10
98
196
294
392

output:

result:

ok single line: '410'

Test #69:

score: 7

Accepted

time: 0ms

memory: 3656kb

input:

148 100 10000 5
98
108
118
128
138

output:

result:

ok single line: '150'

Test #70:

score: 7

Accepted

time: 0ms

memory: 3880kb

input:

206 100 10000 5
98
108
118
128
196

output:

result:

ok single line: '210'

Test #71:

score: 7

Accepted

time: 0ms

memory: 3880kb

input:

216 100 10000 5
98
108
118
196
206

output:

result:

ok single line: '220'

Test #72:

score: 7

Accepted

time: 0ms

memory: 3724kb

input:

304 100 10000 5
98
108
118
196
294

output:

result:

ok single line: '310'

Test #73:

score: 7

Accepted

time: 0ms

memory: 3884kb

input:

226 100 10000 5
98
108
196
206
216

output:

result:

ok single line: '230'

Test #74:

score: 7

Accepted

time: 0ms

memory: 3812kb

input:

304 100 10000 5
98
108
196
206
294

output:

result:

ok single line: '310'

Test #75:

score: 7

Accepted

time: 0ms

memory: 3884kb

input:

314 100 10000 5
98
108
196
294
304

output:

result:

ok single line: '320'

Test #76:

score: 7

Accepted

time: 0ms

memory: 3652kb

input:

402 100 10000 5
98
108
196
294
392

output:

result:

ok single line: '410'

Test #77:

score: 7

Accepted

time: 0ms

memory: 3648kb

input:

236 100 10000 5
98
196
206
216
226

output:

result:

ok single line: '240'

Test #78:

score: 7

Accepted

time: 0ms

memory: 3668kb

input:

304 100 10000 5
98
196
206
216
294

output:

result:

ok single line: '310'

Test #79:

score: 7

Accepted

time: 0ms

memory: 3600kb

input:

314 100 10000 5
98
196
206
294
304

output:

result:

ok single line: '320'

Test #80:

score: 7

Accepted

time: 0ms

memory: 3648kb

input:

402 100 10000 5
98
196
206
294
392

output:

result:

ok single line: '410'

Test #81:

score: 7

Accepted

time: 0ms

memory: 3664kb

input:

324 100 10000 5
98
196
294
304
314

output:

result:

ok single line: '330'

Test #82:

score: 7

Accepted

time: 0ms

memory: 3908kb

input:

402 100 10000 5
98
196
294
304
392

output:

result:

ok single line: '410'

Test #83:

score: 7

Accepted

time: 0ms

memory: 3916kb

input:

412 100 10000 5
98
196
294
392
402

output:

result:

ok single line: '420'

Test #84:

score: 7

Accepted

time: 0ms

memory: 3672kb

input:

500 100 10000 5
98
196
294
392
490

output:

result:

ok single line: '510'

Test #85:

score: 7

Accepted

time: 0ms

memory: 3832kb

input:

10 2 10 2
1
3

output:

result:

ok single line: '41'

Test #86:

score: 7

Accepted

time: 0ms

memory: 3676kb

input:

100 21 10 2
5
54

output:

result:

ok single line: '140'

Test #87:

score: 7

Accepted

time: 0ms

memory: 3876kb

input:

100 21 10 9
18
21
53
62
85
86
88
90
91

output:

result:

ok single line: '121'

Test #88:

score: 7

Accepted

time: 0ms

memory: 3676kb

input:

100 21 10 10
30
39
40
43
45
49
52
57
70
72

output:

result:

ok single line: '132'

Test #89:

score: 7

Accepted

time: 0ms

memory: 3724kb

input:

156 20 1 10
19
37
54
70
85
99
112
124
135
145

output:

result:

ok single line: '162'

Test #90:

score: 7

Accepted

time: 0ms

memory: 3608kb

input:

156 20 20 10
19
37
54
70
85
99
112
124
135
145

output:

result:

ok single line: '211'

Test #91:

score: 7

Accepted

time: 0ms

memory: 3656kb

input:

156 20 30 10
19
37
54
70
85
99
112
124
135
145

output:

result:

ok single line: '211'

Test #92:

score: 7

Accepted

time: 0ms

memory: 3908kb

input:

10 2 10 0

output:

result:

ok single line: '50'

Test #93:

score: 7

Accepted

time: 0ms

memory: 3608kb

input:

output:

result:

ok single line: '10'

Test #94:

score: 7

Accepted

time: 0ms

memory: 3680kb

input:

output:

result:

ok single line: '20'

Test #95:

score: 7

Accepted

time: 0ms

memory: 3660kb

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:

result:

ok single line: '356'

Test #96:

score: 7

Accepted

time: 0ms

memory: 3604kb

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:

result:

ok single line: '340'

Test #97:

score: 7

Accepted

time: 0ms

memory: 3876kb

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:

result:

ok single line: '340'

Test #98:

score: 7

Accepted

time: 0ms

memory: 3888kb

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:

result:

ok single line: '101'

Test #99:

score: 7

Accepted

time: 3ms

memory: 3680kb

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:

result:

ok single line: '1000'

Test #100:

score: 7

Accepted

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:

result:

ok single line: '1126'

Test #101:

score: 7

Accepted

time: 0ms

memory: 3656kb

input:

1000 42 14 100
8
15
24
35
46
60
71
98
102
113
125
126
159
164
181
183
191
199
208
212
216
217
240
244
264
265
269
275
295
299
308
309
320
321
342
351
389
404
449
468
476
487
502
520
544
556
563
578
580
581
589
593
598
609
610
623
626
631
650
663
668
669
670
679
695
714
740
741
748
759
774
775
794
79...

output:

result:

ok single line: '1151'

Test #102:

score: 7

Accepted

time: 0ms

memory: 3656kb

input:

909 12 12 100
11
21
30
38
45
51
58
66
75
85
96
108
119
129
138
146
153
159
166
174
183
193
204
216
227
237
246
254
261
267
274
282
291
301
312
324
335
345
354
362
369
375
382
390
399
409
420
432
443
453
462
470
477
483
490
498
507
517
528
540
551
561
570
578
585
591
598
606
615
625
636
648
659
669
6...

output:

result:

ok single line: '1207'

Test #103:

score: 7

Accepted

time: 0ms

memory: 3884kb

input:

909 12 13 100
11
21
30
38
45
51
58
66
75
85
96
108
119
129
138
146
153
159
166
174
183
193
204
216
227
237
246
254
261
267
274
282
291
301
312
324
335
345
354
362
369
375
382
390
399
409
420
432
443
453
462
470
477
483
490
498
507
517
528
540
551
561
570
578
585
591
598
606
615
625
636
648
659
669
6...

output:

result:

ok single line: '1207'

Test #104:

score: 7

Accepted

time: 0ms

memory: 3652kb

input:

18 4 5 2
8
15

output:

result:

ok single line: '29'

Test #105:

score: 7

Accepted

time: 0ms

memory: 3812kb

input:

18 4 0 2
8
15

output:

result:

ok single line: '18'

Test #106:

score: 7

Accepted

time: 0ms

memory: 3668kb

input:

18 10 100 2
8
15

output:

result:

ok single line: '20'

Test #107:

score: 7

Accepted

time: 0ms

memory: 3812kb

input:

18 4 100 0

output:

result:

ok single line: '418'

Test #108:

score: 7

Accepted

time: 0ms

memory: 3720kb

input:

65 20 100 3
14
25
33

output:

result:

ok single line: '172'

Subtask #4:

score: 0

Wrong Answer

Test #109:

score: 0

Wrong Answer

time: 0ms

memory: 3912kb

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: 3656kb

input:

1000000000000 1 1000000 0

output:

1000000000000000000

result:

wrong answer 1st lines differ - expected: '1000000999999000000', found: '1000000000000000000'

Subtask #6:

score: 0

Skipped

Dependency #1:

Subtask #7:

score: 0

Skipped