QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#767017#8268. Tycho_8_8_0 0ms5756kbC++201.2kb2024-11-20 19:36:052024-11-20 19:36:08

Judging History

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

  • [2024-11-20 19:36:08]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:5756kb
  • [2024-11-20 19:36:05]
  • 提交

answer

#include <bits/stdc++.h> 

using namespace std;

typedef long long ll;

const int N = (int)1e3 + 12;

const ll inf = 11e17;


ll b, p, d, n, a[N], dp[N][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 = 0; i <= n; i++) {
        for(int j = 0; j < p; j++) {
            dp[i][j] = inf;
        }
    }
    dp[0][0] = 0;
    for(int i = 0; i <= n; i++) {
        dp[i][0] = min(dp[i][p - 1] + 1, dp[i][0]);
        for(int j = 0; j < p; j++) {
            if(dp[i][j] == inf) continue;
            int pr = (j ? j - 1 : p - 1);
            dp[i][j] = min(dp[i][j], dp[i][pr] + 1);
            ll k = (j + a[i + 1] - a[i]) % p;
            dp[i + 1][k] = min(dp[i + 1][k], dp[i][j] + get(j + 1, j + a[i + 1] - a[i] - 1) * d + a[i + 1] - a[i]);
        }
    }
    ll res = dp[n][0];
    for(int i = 1; i < p; i++) {
        res = min(res, dp[n][i]);
    }
    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: 8
Accepted
time: 0ms
memory: 3600kb

input:

1000000000000 1 1000000 0

output:

1000000999999000000

result:

ok single line: '1000000999999000000'

Test #2:

score: 8
Accepted
time: 0ms
memory: 5756kb

input:

100 10 11 10
10
11
20
30
38
49
50
60
70
90

output:

122

result:

ok single line: '122'

Test #3:

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

input:

100 10 11 15
1
5
9
15
24
25
39
40
45
66
75
79
85
95
97

output:

178

result:

wrong answer 1st lines differ - expected: '138', found: '178'

Subtask #2:

score: 0
Wrong Answer

Test #11:

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

input:

108 100 10000 5
10
20
30
40
98

output:

10108

result:

wrong answer 1st lines differ - expected: '110', found: '10108'

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Wrong Answer

Test #109:

score: 15
Accepted
time: 0ms
memory: 3596kb

input:

1000000000000 1 1000000 0

output:

1000000999999000000

result:

ok single line: '1000000999999000000'

Test #110:

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

input:

108 100 10000 5
10
20
30
40
98

output:

10108

result:

wrong answer 1st lines differ - expected: '110', found: '10108'

Subtask #5:

score: 0
Skipped

Dependency #2:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%

Subtask #7:

score: 0
Skipped

Dependency #1:

0%