QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#765095#8268. Tycho_8_8_#0 1ms7816kbC++201.5kb2024-11-20 12:04:422024-11-20 12:04:47

Judging History

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

  • [2024-11-20 12:04:47]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:7816kb
  • [2024-11-20 12:04:42]
  • 提交

answer

#include <bits/stdc++.h> 

using namespace std;

typedef long long ll;

const int N = (int)1e6 + 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 - max(0ll, (l - 1)) / p;
}
void test() {
    cin >> b >> p >> d >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for(int i = 1; i <= n; i++) {
        dp[i] = inf;
        for(int j = i - 1; j >= 0; --j) {
            ll x = get(t[j] + 1, t[j] + (a[i] - a[j]) - 1) * d;
            ll v = dp[j] + x + (a[i] - a[j]);
            if(v < dp[i]) {
                dp[i] = v;
                t[i] = t[j] + (a[i] - a[j]);        
            }
            if(x) {
                ll nx = (t[j] + p - 1) / p * p;
                v = (nx - t[j]) + get(nx + 1, nx + (a[i] - a[j]) - 1) * d + (a[i] - a[j]) + dp[j];
                // cout << j << ' ' << v << ' ' << nx - t[j] << '\n';
                if(v < dp[i]) {
                    dp[i] = v;
                    t[i] = nx + (a[i] - a[j]);
                }
            }   
        }
    }
    ll res = inf;
    for(int i = 0; i <= n; i++) {   
        res = min(res, dp[i] + get(t[i] + 1, b) * d + (b - a[i]));
        ll nx = (t[i] + p - 1) / p * p;
        res = min(res, dp[i] + (b - a[i]) + (nx - t[i]) + get(nx + 1, nx + (b - a[i]) - 1) * d);
    }
    cout << res << '\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: 3640kb

input:

1000000000000 1 1000000 0

output:

1000000000000000000

result:

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

Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 5
Accepted
time: 1ms
memory: 7788kb

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

input:

118 100 10000 5
10
20
30
98
108

output:

120

result:

ok single line: '120'

Test #13:

score: 5
Accepted
time: 1ms
memory: 7692kb

input:

206 100 10000 5
10
20
30
98
196

output:

210

result:

ok single line: '210'

Test #14:

score: 5
Accepted
time: 1ms
memory: 7816kb

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

input:

206 100 10000 5
10
20
98
108
196

output:

210

result:

ok single line: '210'

Test #16:

score: 5
Accepted
time: 1ms
memory: 7744kb

input:

216 100 10000 5
10
20
98
196
206

output:

220

result:

ok single line: '220'

Test #17:

score: 5
Accepted
time: 1ms
memory: 7764kb

input:

304 100 10000 5
10
20
98
196
294

output:

310

result:

ok single line: '310'

Test #18:

score: 5
Accepted
time: 1ms
memory: 7744kb

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

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

input:

216 100 10000 5
10
98
108
196
206

output:

220

result:

ok single line: '220'

Test #21:

score: 5
Accepted
time: 1ms
memory: 7812kb

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

input:

226 100 10000 5
10
98
196
206
216

output:

230

result:

ok single line: '230'

Test #23:

score: 5
Accepted
time: 1ms
memory: 7684kb

input:

304 100 10000 5
10
98
196
206
294

output:

310

result:

ok single line: '310'

Test #24:

score: 5
Accepted
time: 1ms
memory: 7764kb

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

input:

402 100 10000 5
10
98
196
294
392

output:

410

result:

ok single line: '410'

Test #26:

score: 5
Accepted
time: 1ms
memory: 7752kb

input:

148 100 10000 5
98
108
118
128
138

output:

150

result:

ok single line: '150'

Test #27:

score: 5
Accepted
time: 1ms
memory: 7816kb

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

input:

216 100 10000 5
98
108
118
196
206

output:

220

result:

ok single line: '220'

Test #29:

score: 5
Accepted
time: 1ms
memory: 7816kb

input:

304 100 10000 5
98
108
118
196
294

output:

310

result:

ok single line: '310'

Test #30:

score: 5
Accepted
time: 1ms
memory: 7816kb

input:

226 100 10000 5
98
108
196
206
216

output:

230

result:

ok single line: '230'

Test #31:

score: 5
Accepted
time: 1ms
memory: 7748kb

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

input:

314 100 10000 5
98
108
196
294
304

output:

320

result:

ok single line: '320'

Test #33:

score: 5
Accepted
time: 1ms
memory: 7760kb

input:

402 100 10000 5
98
108
196
294
392

output:

410

result:

ok single line: '410'

Test #34:

score: 5
Accepted
time: 1ms
memory: 7816kb

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

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

input:

314 100 10000 5
98
196
206
294
304

output:

320

result:

ok single line: '320'

Test #37:

score: 5
Accepted
time: 1ms
memory: 7760kb

input:

402 100 10000 5
98
196
206
294
392

output:

410

result:

ok single line: '410'

Test #38:

score: 5
Accepted
time: 1ms
memory: 7744kb

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

input:

402 100 10000 5
98
196
294
304
392

output:

410

result:

ok single line: '410'

Test #40:

score: 5
Accepted
time: 1ms
memory: 7668kb

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

input:

500 100 10000 5
98
196
294
392
490

output:

510

result:

ok single line: '510'

Test #42:

score: 5
Accepted
time: 1ms
memory: 7740kb

input:

10 2 10 2
1
3

output:

41

result:

ok single line: '41'

Test #43:

score: 5
Accepted
time: 1ms
memory: 7764kb

input:

100 21 10 2
5
54

output:

140

result:

ok single line: '140'

Test #44:

score: 5
Accepted
time: 1ms
memory: 7696kb

input:

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

output:

121

result:

ok single line: '121'

Test #45:

score: 0
Wrong Answer
time: 0ms
memory: 7760kb

input:

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

output:

126

result:

wrong answer 1st lines differ - expected: '132', found: '126'

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Wrong Answer

Test #109:

score: 0
Wrong Answer
time: 0ms
memory: 3584kb

input:

1000000000000 1 1000000 0

output:

1000000000000000000

result:

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

Subtask #5:

score: 0
Skipped

Dependency #2:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%

Subtask #7:

score: 0
Skipped

Dependency #1:

0%