# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
224047 | shenxy | Collecting Stamps 3 (JOI20_ho_t3) | C++11 | 5 ms | 768 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <cstdio>
#include <algorithm>
#define int long long
using namespace std;
const int INF = 1000000000000000000;
int N, L, X[202], T[202];
int dist[202][202][201][2];
int32_t main() {
scanf("%lld %lld", &N, &L);
for (int i = 1; i <= N; ++i) scanf("%lld", &X[i]);
for (int i = 1; i <= N; ++i) scanf("%lld", &T[i]);
X[0] = 0;
X[N + 1] = L;
for (int i = 0; i < N + 2; ++i) {
for (int j = 0; j < N + 2; ++j) dist[i][j][0][0] = dist[i][j][0][1] = INF;
}
dist[0][N + 1][0][0] = dist[0][N + 1][0][1] = 0;
int ans = 0;
for (int i = 1; i <= N; ++i) {
for (int j = 0; j <= N; ++j) {
for (int k = N + 1; k > j; --k) {
dist[j][k][i][0] = dist[j][k][i][1] = INF;
if (j != 0) dist[j][k][i][1] = min(dist[j][k][i][1], min(dist[j - 1][k][i][1] + X[j] - X[j - 1], dist[j - 1][k][i][0] + L - X[k] + X[j]));
if (k != N + 1) dist[j][k][i][0] = min(dist[j][k][i][0], min(dist[j][k + 1][i][0] + X[k + 1] - X[k], dist[j][k + 1][i][1] + L - X[k] + X[j]));
if (j != 0 && min(dist[j - 1][k][i - 1][1] + X[j] - X[j - 1], dist[j - 1][k][i - 1][0] + L - X[k] + X[j]) <= T[j]) dist[j][k][i][1] = min(dist[j][k][i][1], min(dist[j - 1][k][i - 1][1] + X[j] - X[j - 1], dist[j - 1][k][i - 1][0] + L - X[k] + X[j]));
if (k != N + 1 && min(dist[j][k + 1][i - 1][0] + X[k + 1] - X[k], dist[j][k + 1][i - 1][1] + L - X[k] + X[j]) <= T[k]) dist[j][k][i][0] = min(dist[j][k][i][0], min(dist[j][k + 1][i - 1][0] + X[k + 1] - X[k], dist[j][k + 1][i - 1][1] + L - X[k] + X[j]));
if (dist[j][k][i][0] < INF || dist[j][k][i][1] < INF) ans = max(ans, i);
}
}
}
printf("%lld", ans);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |