Submission #1253727

#TimeUsernameProblemLanguageResultExecution timeMemory
1253727gry3125Collecting Stamps 3 (JOI20_ho_t3)C++20
0 / 100
58 ms135236 KiB
#include <bits/stdc++.h> #define pb push_back #define ll long long int #define all(v) (v).begin(),(v).end() #define fi first #define se second using namespace std; ll n, l; int mx = 0; ll dp[205][205][2][205] = { }; int main() { cin >> n >> l; vector<ll> x(n+5), t(n+5); for (int i = 1; i <= n; i++) cin >> x[i]; for (int i = 1; i <= n; i++) cin >> t[i]; for (int i = 0; i < 205; i++) { for (int j = 0; j < 205; j++) { for (int k = 0; k < 205; k++) { dp[i][j][0][k] = 1e18; dp[i][j][1][k] = 1e18; } } } x[n+1] = l; dp[n+1][0][0][0] = 0; dp[n+1][0][1][0] = 0; if (1) { // dp[n+1][?][1][?] int cur = 0; for (int i = 1; i <= n; i++) { if (x[i] <= t[i]) cur++; dp[n+1][i][1][cur] = min(dp[n+1][i][1][cur], x[i]); } // dp[?][0][0][?] cur = 0; for (int i = n; i > 0; i--) { if (l-x[i] <= t[i]) cur++; dp[i][0][0][cur] = min(dp[i][0][0][cur], l-x[i]); } } for (int i = n; i > 0; i--) { for (int j = 1; j < i; j++) { for (int k = 1; k <= n; k++) { // dp[i][j][0][?]: i+1 -> i ll cur = dp[i+1][j][0][k] + x[i+1] - x[i]; dp[i][j][0][k] = min(dp[i][j][0][k], cur); cur = dp[i+1][j][0][k-1] + x[i+1] - x[i]; if (cur <= t[i]) { dp[i][j][0][k] = min(dp[i][j][0][k], cur); } // dp[i][j][0][?]: j -> i cur = dp[i+1][j][1][k] + x[i] - x[j]; dp[i][j][0][k] = min(dp[i][j][0][k], cur); cur = dp[i+1][j][1][k-1] + x[i] - x[j]; if (cur <= t[i]) { dp[i][j][0][k] = min(dp[i][j][0][k], cur); } // dp[i][j][1][?]: j-1 -> j cur = dp[i][j-1][1][k] + x[j] - x[j-1]; dp[i][j][1][k] = min(dp[i][j][1][k], cur); cur = dp[i][j-1][1][k-1] + x[j] - x[j-1]; if (cur <= t[j]) { dp[i][j][1][k] = min(dp[i][j][1][k], cur); } // dp[i][j][1][?]: i -> j cur = dp[i][j-1][0][k] + l - x[i] + x[j]; dp[i][j][1][k] = min(dp[i][j][1][k], cur); cur = dp[i][j-1][0][k-1] + l - x[i] + x[j]; if (cur <= t[j]) { dp[i][j][1][k] = min(dp[i][j][1][k], cur); } } } } for (int i = 0; i <= n+1; i++) { for (int j = 0; j <= n+1; j++) { for (int k = 0; k <= n; k++) { if (dp[i][j][0][k] < 1e18) mx = max(mx, k); if (dp[i][j][1][k] < 1e18) mx = max(mx, k); } } } cout << mx; 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...