Submission #669490

#TimeUsernameProblemLanguageResultExecution timeMemory
669490GrandTiger1729Collecting Stamps 3 (JOI20_ho_t3)C++17
100 / 100
162 ms126148 KiB
#include <iostream> using namespace std; const long long INF = 1e18; int main(){ int n; long long L; cin >> n >> L; long long a[n], b[n]; for (int i = 0; i < n; i++){ cin >> a[i]; } for (int i = 0; i < n; i++){ cin >> b[i]; } auto idx = [&](int i) -> int { return (i % n + n) % n; }; auto dis = [&](long long x, long long y) -> long long { if (x > y) swap(x, y); return min(y - x, x + L - y); }; long long dp[n][n][n + 1][2]{}; // [l, r], pickcnt, cur(l, r) => min time fill_n(&dp[0][0][0][0], sizeof(dp) / sizeof(long long), INF); for (int i = 0; i < n; i++){ dp[i][i][min(a[i], L - a[i]) <= b[i]][0] = dp[i][i][min(a[i], L - a[i]) <= b[i]][1] = min(a[i], L - a[i]); } for (int t = 0; t < n - 1; t++){ for (int l = n - 1; l >= 0; l--){ int r = idx(l + t); for (int i = 0; i < n; i++){ if (dp[l][r][i][0] + dis(a[l], a[idx(l - 1)]) <= b[idx(l - 1)]) dp[idx(l - 1)][r][i + 1][0] = min(dp[idx(l - 1)][r][i + 1][0], dp[l][r][i][0] + dis(a[l], a[idx(l - 1)])); if (dp[l][r][i][1] + dis(a[r], a[idx(l - 1)]) <= b[idx(l - 1)]) dp[idx(l - 1)][r][i + 1][0] = min(dp[idx(l - 1)][r][i + 1][0], dp[l][r][i][1] + dis(a[r], a[idx(l - 1)])); if (dp[l][r][i][0] + dis(a[l], a[idx(r + 1)]) <= b[idx(r + 1)]) dp[l][idx(r + 1)][i + 1][1] = min(dp[l][idx(r + 1)][i + 1][1], dp[l][r][i][0] + dis(a[l], a[idx(r + 1)])); if (dp[l][r][i][1] + dis(a[r], a[idx(r + 1)]) <= b[idx(r + 1)]) dp[l][idx(r + 1)][i + 1][1] = min(dp[l][idx(r + 1)][i + 1][1], dp[l][r][i][1] + dis(a[r], a[idx(r + 1)])); } for (int i = 0; i <= n; i++){ dp[idx(l - 1)][r][i][0] = min(dp[idx(l - 1)][r][i][0], dp[l][r][i][0] + dis(a[l], a[idx(l - 1)])); dp[idx(l - 1)][r][i][0] = min(dp[idx(l - 1)][r][i][0], dp[l][r][i][1] + dis(a[r], a[idx(l - 1)])); dp[l][idx(r + 1)][i][1] = min(dp[l][idx(r + 1)][i][1], dp[l][r][i][0] + dis(a[l], a[idx(r + 1)])); dp[l][idx(r + 1)][i][1] = min(dp[l][idx(r + 1)][i][1], dp[l][r][i][1] + dis(a[r], a[idx(r + 1)])); } } } for (int i = n; i >= 0; i--){ for (int j = 0; j < n; j++){ if (dp[j][idx(j + n - 1)][i][0] != INF || dp[j][idx(j + n - 1)][i][1] != INF){ cout << i; return 0; } } } 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...