QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#753235 | #4931. Comic Binge | MeatInTheMiddle# | WA | 5ms | 82024kb | C++17 | 2.7kb | 2024-11-16 11:54:21 | 2024-11-16 11:54:25 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int dp[1001][1001][10][2];
int a[1001], b[1001], apsum[1001];
int range_sum(int l, int r) {
if (l > r) return 0;
return apsum[r] - apsum[l - 1];
}
const int inf = 0x3f3f3f3f;
void solve() {
int n;
cin >> n;
memset(dp, 0x3f3f3f3f, sizeof dp);
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) cin >> b[i];
for (int i = 1; i <= n; i++) apsum[i] = apsum[i - 1] + a[i];
dp[0][0][0][0] = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
for (int k = 0; k < 10; k++) {
// cout << i << " " << j << " " << k << " ==== \n";
int diff = k + b[i + 1];
int lo = j, hi = i + 1; // possible range: [j, i + 1]
while (lo + 1 < hi) {
int mid = (lo + hi) >> 1;
if (range_sum(j + 1, mid) >= diff) hi = mid;
else lo = mid;
}
int cur_diff = diff - range_sum(j + 1, lo);
// cout << "curdiff: " << diff << " - " << range_sum(j + 1, lo) << " = " << cur_diff << "\n";
// cout << "add: " << range_sum(j + 1, lo) << " (" << j + 1 << " ~ " << lo << ")\n";
if (dp[i][j][k][0] != inf) {
// cout << "!: " << dp[i][j][k][0] << "\n";
if (cur_diff < 10) {
dp[i + 1][lo][cur_diff][1] = min(dp[i + 1][lo][cur_diff][1], dp[i][j][k][0]) + b[i + 1];
// cout << i + 1 << " " << lo << " " << cur_diff << " 1: " << dp[i + 1][lo][cur_diff][1] << "\n";
}
}
if (dp[i][j][k][1] != inf) {
// cout << "!: " << dp[i][j][k][1] << "\n";
dp[i + 1][j][k][0] = min(dp[i + 1][j][k][0], dp[i][j][k][1]);
if (cur_diff < 10) {
dp[i + 1][lo][cur_diff][1] = min(dp[i + 1][lo][cur_diff][1], dp[i][j][k][1]) + b[i + 1];
// cout << i + 1 << " " << lo << " " << cur_diff << " 1: " << dp[i + 1][lo][cur_diff][1] << "\n";
}
// cout << i + 1 << " " << j << " " << k << " 0: " << dp[i + 1][j][k][0] << "\n";
}
}
}
}
int ans = 1e9;
for (int j = 0; j < n; j++) {
for (int k = 0; k < 10; k++) {
for (int l = 0; l < 2; l++) {
ans = min(ans, dp[n][j][k][l] + range_sum(j + 1, n));
}
}
}
cout << ans << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 82024kb
input:
6 3 1 1 1 1 2 1 5 3 3 7 4
output:
13
result:
ok single line: '13'
Test #2:
score: 0
Accepted
time: 4ms
memory: 82000kb
input:
2 2 1 1 1
output:
4
result:
ok single line: '4'
Test #3:
score: 0
Accepted
time: 5ms
memory: 81888kb
input:
1 1 1
output:
2
result:
ok single line: '2'
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 82016kb
input:
161 146 662 336 441 626 77 362 697 911 248 879 40 435 60 518 62 475 908 185 740 435 899 188 673 716 529 524 305 321 998 4 363 598 471 650 379 6 980 971 175 664 328 294 681 201 64 926 608 310 478 404 284 634 239 891 515 433 368 929 457 593 338 432 971 593 134 355 97 658 344 653 592 822 660 403 398 38...
output:
1000000000
result:
wrong answer 1st lines differ - expected: '80587', found: '1000000000'