QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#766942#8268. Tycho_8_8_5 3ms3732kbC++201014b2024-11-20 19:22:512024-11-20 19:22:55

Judging History

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

  • [2024-11-20 19:22:55]
  • 评测
  • 测评结果:5
  • 用时:3ms
  • 内存:3732kb
  • [2024-11-20 19:22:51]
  • 提交

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;
}

详细

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%