Submission #1115053

#TimeUsernameProblemLanguageResultExecution timeMemory
1115053staszic_ojuzCollecting Stamps 3 (JOI20_ho_t3)C++17
100 / 100
159 ms127560 KiB
#include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); long long n,l; cin>>n>>l; vector<long long> tr(n+1); vector<long long> tl(n+1); vector<long long> rd(n+1); vector<long long> ld(n+1); rd[0] = 0; ld[0] = 0; tr[0] = 0; tl[0] = 0; for(int i = 1;i<n+1;i++) { cin>>rd[i]; ld[n-i+1] = l-rd[i]; } for(int i = 1;i<n+1;i++) { cin>>tr[i]; tl[n-i+1] = tr[i]; } long long m = 1000000000; m *=m; long long dp[n+1][n+1][n+1][2]; dp[0][0][0][0] = 0; dp[0][0][0][1] = 0; for(int i = 1;i<n+1;i++) { dp[0][0][i][0] = m; dp[0][0][i][1] = m; } for(int i = 1;i<n+1;i++) { for(int q = 0;q<n+1;q++) { dp[i][0][q][0] = m; dp[i][0][q][1] = m; dp[i][0][q][0] = dp[i-1][0][q][0]-ld[i-1]+ld[i]; if(q!=0 && dp[i-1][0][q-1][0]+ld[i]-ld[i-1] <= tl[i]) { dp[i][0][q][0] = min(dp[i][0][q][0],dp[i-1][0][q-1][0]+ld[i]-ld[i-1]); } dp[i][0][q][1] = 2*dp[i][0][q][0]; } } for(int j = 1;j<n+1;j++) { for(int q = 0;q<n+1;q++) { dp[0][j][q][1] = m; dp[0][j][q][0] = m; dp[0][j][q][1] = dp[0][j-1][q][1]-rd[j-1]+rd[j]; if(q!= 0 &&dp[0][j-1][q-1][1]+rd[j]-rd[j-1] <= tr[j]) { dp[0][j][q][1] = min(dp[0][j][q][1],dp[0][j-1][q-1][1]+rd[j]-rd[j-1]); } dp[0][j][q][0] = 2*dp[0][j][q][1]; } } for(int i = 1;i<n+1;i++) { for(int j = 1;j<n+1;j++) { for(int q = 0;q<n+1;q++) { dp[i][j][q][0] = m; dp[i][j][q][1] = m; if(i+j > n) continue; if(i!= 0) { dp[i][j][q][0] = min(dp[i-1][j][q][0]-ld[i-1]+ld[i],dp[i-1][j][q][1]+rd[j]+ld[i]); } if(q!=0 && dp[i-1][j][q-1][0]+ld[i]-ld[i-1] <= tl[i]) { dp[i][j][q][0] = min(dp[i][j][q][0],dp[i-1][j][q-1][0]+ld[i]-ld[i-1]); } if(q!=0 && dp[i-1][j][q-1][1]+rd[j]+ld[i] <=tl[i]) { dp[i][j][q][0] = min(dp[i][j][q][0],dp[i-1][j][q-1][1]+ld[i]+rd[j]); } if(j != 0) { dp[i][j][q][1] = min(dp[i][j-1][q][0]+ld[i]+rd[j],dp[i][j-1][q][1]-rd[j-1]+rd[j]); } if(q!= 0 && dp[i][j-1][q-1][0] + ld[i]+rd[j] <= tr[j]) { dp[i][j][q][1] = min(dp[i][j][q][1],dp[i][j-1][q-1][0] + ld[i]+rd[j]); } if(q != 0 && dp[i][j-1][q-1][1] + rd[j]-rd[j-1] <= tr[j]) { dp[i][j][q][1] = min(dp[i][j][q][1],dp[i][j-1][q-1][1]-rd[j-1]+rd[j]); } } } } int ans = 0; for(int i = 0;i<n+1;i++) { for(int j = 0;j<n+1;j++) { for(int q = 0;q<n+1;q++) { if(dp[i][j][q][0] < m) ans = max(ans,q); if(dp[i][j][q][1] < m) ans = max(ans,q); } } } 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...