Submission #1208563

#TimeUsernameProblemLanguageResultExecution timeMemory
1208563dima2101Collecting Stamps 3 (JOI20_ho_t3)C++20
0 / 100
1 ms580 KiB
#include <bits/stdc++.h> #define int long long const int MAXN = 202; int per; int dp[MAXN][MAXN][MAXN][2]; int give_best(int l, int r) { return std::min(std::abs(r - l), per - std::abs(r - l)); } signed main() { std::ios::sync_with_stdio(false); std::cin.tie(0); int n; std::cin >> n; std::cin >> per; std::vector<int> x; x.push_back(0); std::vector<int> t; t.push_back(1e9); for (int i = 0; i < n; i++) { int help; std::cin >> help; x.push_back(help); } for (int i = 0; i < n; i++) { int help; std::cin >> help; t.push_back(help); } if (n == 1) { if (t[0] >= std::min(per - x[0], x[0])) { std::cout << 1; } else { std::cout << 0; } return 0; } for (int l = 0; l <= n; l++) { for (int r = 0; r <= n; r++) { for (int j = 0; j <= n; j++) { dp[l][r][j][0] = 1e13; dp[l][r][j][1] = 1e13; } } } int max = 0; dp[1][n][0][0] = 0; dp[1][n][0][1] = 0; for (int len = n - 1; len >= 0; len--) { for (int l = 1; l <= n - len; l++) { int r = l + len - 1; for (int j = 0; j <= (n - len); j++) { if (j > 0 && l > 1) { if (dp[l - 1][r][j - 1][0] + give_best(x[l - 1], x[l - 2]) <= t[l - 1]) { dp[l][r][j][0] = std::min(dp[l][r][j][0], dp[l - 1][r][j - 1][0] + give_best(x[l - 1], x[l - 2])); } else { dp[l][r][j][0] = std::min(dp[l][r][j][0], dp[l - 1][r][j][0] + give_best(x[l - 1], x[l - 2])); } } else if (l > 1) { dp[l][r][j][0] = std::min(dp[l][r][j][0], dp[l - 1][r][j][0] + give_best(x[l - 1], x[l - 2])); } if (j > 0 && r < n) { // std::cout << t[r + 1] << ' ' << give_best(x[(r + 2) % (n + 1)], x[r + 1]) << std::endl; if (dp[l][r + 1][j - 1][1] + give_best(x[(r + 2) % (n + 1)], x[r + 1]) <= t[r + 1]) { dp[l][r][j][1] = std::min(dp[l][r][j][1], dp[l][r + 1][j - 1][1] + give_best(x[(r + 2) % (n + 1)], x[r + 1])); } else { dp[l][r][j][1] = std::min(dp[l][r][j][1], dp[l][r + 1][j][1] + give_best(x[(r + 2) % (n + 1)], x[r + 1])); } } else if (r < n) { dp[l][r][j][1] = std::min(dp[l][r][j][1], dp[l][r + 1][j][1] + give_best(x[(r + 2) % (n + 1)], x[r + 1])); } if (dp[l][r][j][0] < dp[l][r][j][1]) { int help = (r + 1) % (n + 1); int help1 = (l - 1 + n) % (n + 1); dp[l][r][j][1] = std::min(dp[l][r][j][1], dp[l][r][j][0] + give_best(x[help], x[help1])); } else { int help = (r + 1) % (n + 1); int help1 = (l - 1 + n) % (n + 1); dp[l][r][j][0] = std::min(dp[l][r][j][0], dp[l][r][j][1] + give_best(x[help], x[help1])); } // std::cout << l << ' ' << r << ' ' << j << ' ' << dp[l][r][j][0] << ' ' << dp[l][r][j][1] << std::endl; if (dp[l][r][j][0] < 1e13 || dp[l][r][j][1] < 1e13) { max = std::max(max, j); } } } } std::cout << max; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...