Submission #236837

#TimeUsernameProblemLanguageResultExecution timeMemory
236837wwddCollecting Stamps 3 (JOI20_ho_t3)C++14
100 / 100
439 ms135544 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MN = 210; const ll INFL = 1e18; ll dp[2][MN][MN][MN]; ll w[MN],x[MN]; int main() { ll n,len; cin >> n >> len; w[0] = 0; for(int i=0;i<n;i++) { cin >> w[i+1]; } x[0] = -1; for(int i=0;i<n;i++) { cin >> x[i+1]; } for(int i=0;i<2;i++) { for(int j=0;j<=n;j++) { for(int k=0;k<=n+1;k++) { for(int l=0;l<=n;l++) { dp[i][j][k][l] = INFL; } } } } dp[0][0][0][0] = dp[1][0][0][0]= 0; for(int l=0;l<=n;l++) { for(int k=0;k<n;k++) { for(int j=0;j<=n;j++) { for(int i=0;i<2;i++) { if(dp[i][j][k][l] >= INFL) {continue;} ll dr,dl; int nr = (j+k+1)%(n+1); int nl = (j+n)%(n+1); if(i) { int ro = (j+k)%(n+1); dr = ((w[nr]-w[ro])+len)%len; dl = ((w[ro]-w[nl])+len)%len; } else { dr = ((w[nr]-w[j])+len)%len; dl = ((w[j]-w[nl])+len)%len; } int cor = l, col=l; if(dp[i][j][k][l]+dr <= x[nr]) { cor++; } if(dp[i][j][k][l]+dl <= x[nl]) { col++; } dp[1][j][k+1][cor] = min(dp[1][j][k+1][cor],dp[i][j][k][l]+dr); dp[0][nl][k+1][col] = min(dp[0][nl][k+1][col],dp[i][j][k][l]+dl); } } } } int res = 0; for(int i=0;i<2;i++) { for(int j=0;j<=n;j++) { for(int k=0;k<=n+1;k++) { for(int l=0;l<=n;l++) { if(dp[i][j][k][l] < INFL) { res = max(res,l); } } } } } cout << res << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...