This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// dinhmanhhungwillwinioi2024
#include <bits/stdc++.h>
using namespace std;
const int N = 403, MAX = 1e9;
int n, limit, t[N], dp[N][N][N][2];
struct Data {
int pos, t;
Data(int pos = 0, int t = 0):
pos(pos), t(t) {}
} a[N];
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> limit;
for (int i = 1; i <= n; i++)
cin >> a[i].pos;
for (int i = 1; i <= n; i++)
cin >> a[i].t;
if (n == 1) {
if (a[1].pos <= a[1].t || limit - a[1].pos <= a[1].t)
cout << 1;
else cout << 0;
return 0;
}
for (int i = 1; i <= n; i++)
a[i + n] = a[i], a[i + n].pos += limit;
memset(dp, 63, sizeof dp);
bool tmp = (limit - a[n].pos) <= a[n].t;
dp[n][n][tmp][0] = dp[n][n][tmp][1] = limit - a[n].pos;
tmp = (a[n + 1].pos - limit <= a[n + 1].t);
dp[n + 1][n + 1][tmp][0] = dp[n + 1][n + 1][tmp][1] = a[n + 1].pos - limit;
int m = (n << 1), ans = 0;
for (int l = n + 1; l > 0; l--) {
for (int r = l; r <= m; r++) {
for (int k = r - l + 1; k >= 0; k--) {
for (int s = 0; s < 2; s++) {
int cur = dp[l][r][k][s];
if (cur > MAX || r - n >= l) continue;
ans = max(ans, k);
if (r + 1 <= m && (l > n || r + 1 - n < l)) {
int cost = a[r + 1].pos - (s ? a[r].pos : a[l].pos);
if (cost <= MAX && cur + cost < dp[l][r + 1][k + (cur + cost <= a[r + 1].t)][1])
dp[l][r + 1][k + (cur + cost <= a[r + 1].t)][1] = cur + cost;
}
if (l - 1 > 0 && (r <= n || l - 1 > r - n)) {
int cost = (s ? a[r].pos : a[l].pos) - a[l - 1].pos;
if (cost <= MAX && cur + cost < dp[l - 1][r][k + (cur + cost <= a[l - 1].t)][0])
dp[l - 1][r][k + (cur + cost <= a[l - 1].t)][0] = cur + cost;
}
}
}
}
}
cout << ans;
return 0;
}
# | 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... |