Submission #1085820

#TimeUsernameProblemLanguageResultExecution timeMemory
1085820vako_pCollecting Stamps 3 (JOI20_ho_t3)C++14
0 / 100
1 ms4444 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back const int mxN = 205; ll n,x[mxN],t[mxN],L,dp[mxN][mxN][mxN][2],inf = 1e17; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> L; 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 <= n; i++) for(int j = 0; j <= n; j++) for(int k = 0; k <= n; k++){ dp[i][j][k][0] = dp[i][j][k][1] = inf; } dp[0][0][0][0] = dp[0][0][0][1] = 0; x[n + 1] = L; ll ans = 0; for(int k = 1; k <= n; k++){ for(ll i1 = n + 1; i1 >= 1; i1--){ ll i = i1 % (n + 1); if(i1 != n + 1){ ll num = dp[k - 1][(i + 1) % (n + 1)][0][1]; dp[k][i][0][1] = min(num + ((t[i] >= num + x[i + 1] - x[i]) ? (x[i + 1] - x[i]) : inf), inf); dp[k][i][0][0] = min(dp[k][i][0][1] + L - x[i], dp[k][(i + 1) % (n + 1)][0][0]); } for(ll j = 1; j != i1; j++){ ll num = dp[k - 1][i][j - 1][0]; dp[k][i][j][0] = min(num + ((t[j] >= num + x[j] - x[j - 1]) ? (x[j] - x[j - 1]) : inf),inf); dp[k][i][j][0] = min(dp[k][i][j][0], dp[k][i][j - 1][0] + x[j] - x[j - 1]); if(i1 != n + 1){ dp[k][i][j][0] = min(dp[k][i][j][0], dp[k][(i + 1) % (n + 1)][j][0]); } else continue; num = dp[k - 1][(i + 1) % (n + 1)][j][1]; dp[k][i][j][1] = min(min(num + ((t[i] >= num + x[i + 1] - x[i]) ? (x[i + 1] - x[i]) : inf), dp[k][i][j - 1][1]), inf); dp[k][i][j][1] = min(dp[k][i][j][1], dp[k][(i + 1) % (n + 1)][j][1] + x[i + 1] - x[i]); dp[k][i][j][0] = min(dp[k][i][j][0], dp[k][i][j][1] + L - x[i] + x[j]); dp[k][i][j][1] = min(dp[k][i][j][1], dp[k][i][j][0] + L - x[i] + x[j]); } } } 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] < inf or dp[i][j][k][1] < inf) ans = max(ans, (ll)i); } cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...