제출 #924597

#제출 시각아이디문제언어결과실행 시간메모리
924597qwe1rt1yuiop1Collecting Stamps 3 (JOI20_ho_t3)C++14
15 / 100
2119 ms526020 KiB
#include <bits/stdc++.h> #define int long long using namespace std; using pii = pair<int, int>; int n, l; vector<int> x, t; int dis(int a, int b) { assert(0 <= a && 0 <= b && a <= n && b <= n); return min(min(abs(x[a] - x[b]), x[a] + l - x[b]), l - x[a] + x[b]); } void solve() { cin >> n >> l; x.assign(n + 1, 0), t.assign(n + 1, -1); for (int i = 1; i <= n; ++i) cin >> x[i]; for (int i = 1; i <= n; ++i) cin >> t[i]; vector<vector<vector<vector<int>>>> dp(n + 1, vector<vector<vector<int>>>(n + 1, vector<vector<int>>(n + 1, vector<int>(2, LONG_LONG_MAX)))); priority_queue<array<int, 5>> pq; array<int, 5> tmp; dp[0][0][0][0] = dp[0][0][0][1] = 0; pq.emplace(tmp = {0, 0, 0, 0, 0}); pq.emplace(tmp = {0, 0, 0, 0, 1}); while (!pq.empty()) { tmp = pq.top(); pq.pop(); int i = tmp[1], j = tmp[2], k = tmp[3], ll = tmp[4], d = -tmp[0]; if (d != dp[i][j][k][ll]) continue; // cout << d << ' '; if (ll == 0) { if ((j + n) % (n + 1) != k) { if (dp[i][(j + n) % (n + 1)][k][0] > dp[i][j][k][0] + dis(j, (j + n) % (n + 1))) { dp[i][(j + n) % (n + 1)][k][0] = dp[i][j][k][0] + dis(j, (j + n) % (n + 1)); pq.emplace(tmp = {-dp[i][(j + n) % (n + 1)][k][0], i, (j + n) % (n + 1), k, 0}); } if (dp[i][j][k][0] + dis(j, (j + n) % (n + 1)) <= t[(j + n) % (n + 1)]) { if (dp[i + 1][(j + n) % (n + 1)][k][0] > dp[i][j][k][0] + dis(j, (j + n) % (n + 1))) { dp[i + 1][(j + n) % (n + 1)][k][0] = dp[i][j][k][0] + dis(j, (j + n) % (n + 1)); pq.emplace(tmp = {-dp[i + 1][(j + n) % (n + 1)][k][0], i + 1, (j + n) % (n + 1), k, 0}); } } } if (j != (k + 1) % (n + 1)) { if (dp[i][j][(k + 1) % (n + 1)][1] > dp[i][j][k][0] + dis(j, (k + 1) % (n + 1))) { dp[i][j][(k + 1) % (n + 1)][1] = dp[i][j][k][0] + dis(j, (k + 1) % (n + 1)); pq.emplace(tmp = {-dp[i][j][(k + 1) % (n + 1)][1], i, j, (k + 1) % (n + 1), 1}); } if (dp[i][j][k][0] + dis(j, (k + 1) % (n + 1)) <= t[(k + 1) % (n + 1)]) { if (dp[i + 1][j][(k + 1) % (n + 1)][1] > dp[i][j][k][0] + dis(j, (k + 1) % (n + 1))) { dp[i + 1][j][(k + 1) % (n + 1)][1] = dp[i][j][k][0] + dis(j, (k + 1) % (n + 1)); pq.emplace(tmp = {-dp[i + 1][j][(k + 1) % (n + 1)][1], i + 1, j, (k + 1) % (n + 1), 1}); } } } } else { if ((j + n) % (n + 1) != k) { if (dp[i][(j + n) % (n + 1)][k][0] > dp[i][j][k][1] + dis(k, (j + n) % (n + 1))) { dp[i][(j + n) % (n + 1)][k][0] = dp[i][j][k][1] + dis(k, (j + n) % (n + 1)); pq.emplace(tmp = {-dp[i][(j + n) % (n + 1)][k][0], i, (j + n) % (n + 1), k, 0}); } if (dp[i][j][k][1] + dis(k, (j + n) % (n + 1)) <= t[(j + n) % (n + 1)]) { if (dp[i + 1][(j + n) % (n + 1)][k][0] > dp[i][j][k][1] + dis(k, (j + n) % (n + 1))) { dp[i + 1][(j + n) % (n + 1)][k][0] = dp[i][j][k][1] + dis(k, (j + n) % (n + 1)); pq.emplace(tmp = {-dp[i + 1][(j + n) % (n + 1)][k][0], i + 1, (j + n) % (n + 1), k, 0}); } } } if (j != (k + 1) % (n + 1)) { if (dp[i][j][(k + 1) % (n + 1)][1] > dp[i][j][k][1] + dis(k, (k + 1) % (n + 1))) { dp[i][j][(k + 1) % (n + 1)][1] = dp[i][j][k][1] + dis(k, (k + 1) % (n + 1)); pq.emplace(tmp = {-dp[i][j][(k + 1) % (n + 1)][1], i, j, (k + 1) % (n + 1), 1}); } if (dp[i][j][k][1] + dis(k, (k + 1) % (n + 1)) <= t[(k + 1) % (n + 1)]) { if (dp[i + 1][j][(k + 1) % (n + 1)][1] > dp[i][j][k][1] + dis(k, (k + 1) % (n + 1))) { dp[i + 1][j][(k + 1) % (n + 1)][1] = dp[i][j][k][1] + dis(k, (k + 1) % (n + 1)); pq.emplace(tmp = {-dp[i + 1][j][(k + 1) % (n + 1)][1], i + 1, j, (k + 1) % (n + 1), 1}); } } } } } /* for (int i = 0; i < n; ++i) for (int j = 0; j <= n; ++j) for (int k = 0; k <= n; ++k) { if (dp[i][j][k][0] != LONG_LONG_MAX) { if ((j + n) % (n + 1) != k) { dp[i][(j + n) % (n + 1)][k][0] = min(dp[i][(j + n) % (n + 1)][k][0], dp[i][j][k][0] + dis(j, (j + n) % (n + 1))); if (dp[i][j][k][0] + dis(j, (j + n) % (n + 1)) <= t[(j + n) % (n + 1)]) dp[i + 1][(j + n) % (n + 1)][k][0] = min(dp[i + 1][(j + n) % (n + 1)][k][0], dp[i][j][k][0] + dis(j, (j + n) % (n + 1))); } if (j != (k + 1) % (n + 1)) { dp[i][j][(k + 1) % (n + 1)][1] = min(dp[i][j][(k + 1) % (n + 1)][1], dp[i][j][k][0] + dis(j, (k + 1) % (n + 1))); if (dp[i][j][k][0] + dis(j, (k + 1) % (n + 1)) <= t[(k + 1) % (n + 1)]) dp[i + 1][j][(k + 1) % (n + 1)][1] = min(dp[i + 1][j][(k + 1) % (n + 1)][1], dp[i][j][k][0] + dis(j, (k + 1) % (n + 1))); } } if (dp[i][j][k][1] != LONG_LONG_MAX) { if ((j + n) % (n + 1) != k) { dp[i][(j + n) % (n + 1)][k][0] = min(dp[i][(j + n) % (n + 1)][k][0], dp[i][j][k][1] + dis(k, (j + n) % (n + 1))); if (dp[i][j][k][1] + dis(k, (j + n) % (n + 1)) <= t[(j + n) % (n + 1)]) dp[i + 1][(j + n) % (n + 1)][k][0] = min(dp[i + 1][(j + n) % (n + 1)][k][0], dp[i][j][k][1] + dis(k, (j + n) % (n + 1))); } if (j != (k + 1) % (n + 1)) { dp[i][j][(k + 1) % (n + 1)][1] = min(dp[i][j][(k + 1) % (n + 1)][1], dp[i][j][k][1] + dis(k, (k + 1) % (n + 1))); if (dp[i][j][k][1] + dis(k, (k + 1) % (n + 1)) <= t[(k + 1) % (n + 1)]) dp[i + 1][j][(k + 1) % (n + 1)][1] = min(dp[i + 1][j][(k + 1) % (n + 1)][1], dp[i][j][k][1] + dis(k, (k + 1) % (n + 1))); } } } */ int ans = 0; for (int i = 0; i <= n; ++i) for (int j = 0; j <= n; ++j) for (int k = 0; k <= n; ++k) for (int l = 0; l < 2; ++l) if (dp[i][j][k][l] != LONG_LONG_MAX) ans = max(ans, i); cout << ans << '\n'; } /* 6 25 3 4 7 17 21 23 11 7 17 10 8 10 5 20 4 5 8 13 17 18 23 15 7 10 4 19 3 7 12 14 2 0 5 4 10 87 9 23 33 38 42 44 45 62 67 78 15 91 7 27 31 53 12 91 89 46 */ signed main() { ios::sync_with_stdio(0); cin.tie(0); solve(); 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...