QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#226508 | #2500. Collecting Stamps 3 | Camillus | 0 | 19ms | 214528kb | C++20 | 2.3kb | 2023-10-26 01:31:22 | 2023-10-26 01:31:23 |
Judging History
answer
/// @author Camillus
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
int dp[300][300][300][2];
int x[300][2];
int t[300][2];
int min_equal(int &first, int second) {
return first = min(first, second);
}
signed main() {
#ifndef LOCAL
ios::sync_with_stdio(false);
cin.tie(nullptr);
#else
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
for (auto &a : dp) {
for (auto &b : a) {
for (auto &c : b) {
for (auto &d : c) {
d = INT32_MAX;
}
}
}
}
dp[0][0][0][0] = 0;
int n, l;
cin >> n >> l;
for (int i = 1; i <= n; i++) {
cin >> x[i][0];
x[n - i + 1][1] = l - x[i][0];
}
for (int i = 1; i <= n; i++) {
cin >> t[i][0];
t[n - i + 1][1] = t[i][0];
}
int ans = 0;
auto dist = [&l](int x, int y) {
return min(abs(x - y), l - abs(x - y));
};
for (int c = 0; c <= n; c++) {
for (int l = 0; l <= n; l++) {
for (int r = 0; r <= n; r++) {
for (int tA : {0, 1}) {
if (dp[c][l][r][tA] == INT32_MAX) {
continue;
} else {
ans = max(ans, c);
}
if (l + r >= n) {
continue;
}
int posA = (tA == 0 ? x[l][0] : x[r][1]);
for (int tB : {0, 1}) {
if (l + (tB == 0) > n || r + (tB == 1) > n) {
continue;
}
int posB = (tB == 0 ? x[l + 1][0] : x[r + 1][1]);
int timeB = (tB == 0 ? t[l + 1][0] : t[r + 1][1]);
int cur = dp[c][l][r][tA] + dist(posA, posB);
if (cur <= timeB) {
min_equal(dp[c + 1][l + (tB == 0)][r + (tB == 1)][tB], cur);
} else {
min_equal(dp[c][l + (tB == 0)][r + (tB == 1)][tB], cur);
}
}
}
}
}
}
cout << ans << '\n';
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 5
Accepted
time: 8ms
memory: 214528kb
input:
5 180 137 149 164 167 171 18 76 14 55 116
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 19ms
memory: 214356kb
input:
5 198 5 12 18 190 192 16 43 200 33 0
output:
4
result:
ok single line: '4'
Test #3:
score: 0
Accepted
time: 3ms
memory: 214296kb
input:
9 198 3 17 22 33 43 44 48 54 65 0 17 29 32 38 46 45 54 66
output:
5
result:
ok single line: '5'
Test #4:
score: 0
Accepted
time: 0ms
memory: 214352kb
input:
6 171 22 30 46 85 96 149 18 179 19 69 87 96
output:
3
result:
ok single line: '3'
Test #5:
score: 0
Accepted
time: 3ms
memory: 214308kb
input:
7 198 5 8 14 188 191 194 197 7 18 50 69 80 35 8
output:
7
result:
ok single line: '7'
Test #6:
score: -5
Wrong Answer
time: 12ms
memory: 214484kb
input:
12 198 71 72 83 94 108 112 119 140 142 143 166 174 124 119 124 111 91 94 85 48 60 63 40 32
output:
11
result:
wrong answer 1st lines differ - expected: '9', found: '11'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%