Submission #391230

#	Time	Username	Problem	Language	Result	Execution time	Memory
391230		lukameladze	Collecting Stamps 3 (JOI20_ho_t3)	C++14	15 / 100	76 ms	106056 KiB

ho_t3

# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
using namespace std;
const int N=205;
long long  n,x[N],dp[N][N][N][2],t[N],le,ri,l,ans,ff,ff1;
long long go(long long x, long long xx) {
     if (x<xx) swap(x,xx);
     return min(x-xx,xx-x+l);
}
long long mn(long long a, long long b , long long c) {
     return(min(a,min(b,c)));
}
int main() {
     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 le=0; le<=n+1; le++) {
          for (int ri=0; ri<=n+1; ri++) {
               for (int cnt=0; cnt<=n+1; cnt++) {
                    dp[le][ri][cnt][0]=dp[le][ri][cnt][1]=1e17;
               }
          }
     }
     dp[0][0][0][0]=0;
     dp[0][0][0][1]=0;
     x[0]=l;
     for (int sz=1; sz<=n; sz++) {
          for (int ri=0; ri<=sz; ri++) {
               if (ri==sz) le=0; 
                    else le=n-(sz-ri)+1;
               ff=ff1=0;
                 if (le<ri && le!=0) continue;
               for (int cnt=0; cnt<=sz; cnt++) {
                  
                    dp[le][ri][cnt][0]=mn(dp[le][ri][cnt][0],dp[(le+1)%(n+1)][ri][cnt][0]+go(x[(le+1)%(n+1)],x[le]),dp[(le+1)%(n+1)][ri][cnt][1]+go(x[ri], x[le]));
                    if (ri)
                    dp[le][ri][cnt][1]=mn(dp[le][ri][cnt][1],dp[le][ri-1][cnt][1]+go(x[ri-1], x[ri]),dp[le][ri-1][cnt][0]+go(x[le],x[ri]));
                  /* if (cnt<sz) {
                         if (dp[le][ri][cnt][0]<=t[le]) {
                              dp[le][ri][cnt+1][0]=min(dp[le][ri][cnt+1][0],dp[le][ri][cnt][0]);
                         }
                         if (dp[le][ri][cnt][1]<=t[ri] && !ff1) {
                              dp[le][ri][cnt+1][1]=min(dp[le][ri][cnt+1][1],dp[le][ri][cnt][1]);
                         }
                    }*/
                 //  if (cnt==5 && dp[le][ri][cnt][1]<1e9)cout<<le<<" "<<ri<<" "<<cnt<<" "<<dp[le][ri][cnt][1]<<endl;
                    if (dp[le][ri][cnt][0]<(long long)1e17 || dp[le][ri][cnt][1]<(long long)1e17) { ans=max(ans,(long long)cnt);}
               }
       //        if (sz==2 && le==6 && ri==1) cout<<dp[6][1][2][1]<<endl;
               for (int cnt=sz; cnt>=1; cnt--) {
                    if (dp[le][ri][cnt-1][1]<=t[ri] && !ff) {
                         ff=1;
                          
                         dp[le][ri][cnt][1]=min(dp[le][ri][cnt][1],dp[le][ri][cnt-1][1]);
                         //if (sz==2 && le==6 && ri==1 && cnt==2) 
                         // cout<<dp[le][ri][cnt][1]<<endl;
                    }
                    if (dp[le][ri][cnt-1][0]<=t[le] && !ff1) {
                         ff1=1;
                         dp[le][ri][cnt][0]=min(dp[le][ri][cnt][0],dp[le][ri][cnt-1][0]);
                    }
                    if (dp[le][ri][cnt][0]<(long long)1e17 || dp[le][ri][cnt][1]<(long long)1e17) { ans=max(ans,(long long)cnt);}
               }
          }
     }
     //cout<<dp[6][1][2][0]<<endl;
     cout<<ans<<endl;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 75