QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#767017 | #8268. Tycho | _8_8_ | 0 | 0ms | 5756kb | C++20 | 1.2kb | 2024-11-20 19:36:05 | 2024-11-20 19:36:08 |
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;
}
詳細信息
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%