Submission #856387

#TimeUsernameProblemLanguageResultExecution timeMemory
856387qthang2k11Collecting Stamps 3 (JOI20_ho_t3)C++17
100 / 100
97 ms513104 KiB
// 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...