Submission #391268

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

ho_t3

# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
using namespace std;
const int N=215;
long long  n,x[N],dp[N][N][N][2],t[N],le,ri,l,ans,ff,ff1,dist;
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 check(int le ,int ri) {
     if (le==0) return 1;
     if (le<ri) return 0;
     return 1;
}
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++) {
                  if (le && check((le+1)%(n+1),ri))
                  {
                       dist=min(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 (dist<=t[le]) dp[le][ri][cnt+1][0]=min(dp[le][ri][cnt+1][0],dist);
                        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) {
                    dist=min(dp[le][ri-1][cnt][1]+go(x[ri-1], x[ri]),dp[le][ri-1][cnt][0]+go(x[le],x[ri]));
                   // if (dist<=t[ri]) dp[le][ri][cnt+1][1]=min(dp[le][ri][cnt+1][1],dist);
                    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 (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 (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