Submission #1114702

#TimeUsernameProblemLanguageResultExecution timeMemory
1114702tkwiatkowskiJJOOII 2 (JOI20_ho_t2)C++17
0 / 100
1 ms336 KiB
#include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,l; cin>>n>>l; vector<int> tr(n); vector<int> tl(n); vector<int> rd(n+1); vector<int> ld(n+1); vector<pair<int,int>> cl(n); vector<pair<int,int>> cr(n); rd[0] = 0; ld[0] = 0; for(int i = 0;i<n;i++) { //cin>>rd[i+1]; //ld[n-i] = l-rd[i+1]; cin>>cr[i].first; cr[i].first%=l; cl[n-i-1].first = l-cr[i].first; } for(int i = 0;i<n;i++) { //cin>>tr[i]; //tl[n-i-1] = tr[i]; cin>>cr[i].second; cl[n-i-1].second = cr[i].second; } sort(cl.begin(),cl.end()); sort(cr.begin(),cr.end()); for(int i = 0;i<n;i++) { rd[i+1] = cr[i].first; ld[i+1] = cl[i].first; tr[i] = cr[i].second; tl[i] = cl[i].second; } 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-1]) { //if(q==1&&i==1) cout<<"d"<<ld[i]<<" "<<ld[i-1]<<"\n"; 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-1]) { 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!= 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-1]) { 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-1]) { dp[i][j][q][0] = min(dp[i][j][q][0],dp[i-1][j][q-1][0]+ld[i]+rd[j]); } //if((i == 1 && j == 1)&&(q == 1)) //{cout<<"a"<<"\n";} if(j != 0) { /*if((i == 1 && j == 1)&&(q == 1)) { cout<<dp[i][j][q][1]<<"\n"; }*/ 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((i == 1 && j == 1)&&(q == 1)) { cout<<dp[i][j][q][1]<<"\n"; }*/ } if(q!= 0 && dp[i][j-1][q-1][0] + ld[i]+rd[j] <= tr[j-1]) { //if((i == 1 && j == 1)&&(q == 1)) cout<<"b"<<"\n"; 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-1]) { //if((i == 1 && j == 1)&&(q == 1)) cout<<"a"<<"\n"; dp[i][j][q][1] = min(dp[i][j][q][1],dp[i][j-1][q-1][0]-rd[j-1]+rd[j]); } } } } /*for(int i = 0;i<n+1;i++) { for(int j = 0;j<n+1;j++) { for(int q = 0;q<n+1;q++) { for(int w = 0;w<2;w++) { cout<<dp[i][j][q][w]<<" dp["<<i<<"]["<<j<<"]["<<q<<"]["<<w<<"]\n";; } } } }*/ 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...