Submission #489595

#	Time	Username	Problem	Language	Result	Execution time	Memory
489595		bigDuck	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	66 ms	70448 KiB

ho_t3

#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll

int n, l, x[201], t[201];

int dp[202][202][202][2];



int32_t main(){
INIT
cin>>n>>l;
for(int i=1; i<=n; i++){
    cin>>x[i];
}
for(int i=1; i<=n; i++){
    cin>>t[i];
}

int res=0;
x[n+1]=l;
for(int cnt=0; cnt<=n; cnt++){
    for(int i=(n+1); i>=1; i--){
        for(int j=0; j<i; j++){

                if( (dp[cnt][i][j][1]!=0)  ){
                    dp[cnt][i][j][0]=(dp[cnt][i][j][0]==0 )?(dp[cnt][i][j][1]+(l-x[i]+x[j]) ):( min(dp[cnt][i][j][0], dp[cnt][i][j][1]+l-x[i]+x[j]) );
                }

            if( (dp[cnt][i][j][0]!=0) || ( (i==(n+1)) && (j==0 ) && (cnt==0) ) ){
                res=max(res, cnt);


                if( (dp[cnt][i][j][0]+x[j+1]-x[j])<=t[j+1] ){
                    dp[cnt+1][i][j+1][0]=(dp[cnt+1][i][j+1][0]==0)?( (dp[cnt][i][j][0]+x[j+1]-x[j]) ):( min((dp[cnt][i][j][0]+x[j+1]-x[j]), dp[cnt+1][i][j+1][0] ) );
                }
                else{
                    dp[cnt][i][j+1][0]=(dp[cnt][i][j+1][0]==0 )?( dp[cnt][i][j][0]+x[j+1]-x[j] ):(min(dp[cnt][i][j+1][0], dp[cnt][i][j][0]+x[j+1]-x[j] ) );
                }
            }


                if(dp[cnt][i][j][0]!=0){
                    dp[cnt][i][j][1]=(dp[cnt][i][j][1]==0 )?(dp[cnt][i][j][0]+l-x[i]+x[j] ):(min(dp[cnt][i][j][1], dp[cnt][i][j][0]+l-x[i]+x[j] ) );
                }

            if( (dp[cnt][i][j][1]!=0) || ( (i==(n+1)) && (j==0) && (cnt==0) )  ){
                res=max(res, cnt);
                if(dp[cnt][i][j][0]!=0){
                    dp[cnt][i][j][1]=(dp[cnt][i][j][1]==0 )?(dp[cnt][i][j][0]+l-x[i]+x[j] ):(min(dp[cnt][i][j][1], dp[cnt][i][j][0]+l-x[i]+x[j] ) );
                }
                if( ( dp[cnt][i][j][1]+x[i]-x[i-1] )<=t[i-1] ){
                    dp[cnt+1][i-1][j][1]=(dp[cnt+1][i-1][j][1]==0 )?(dp[cnt][i][j][1]+x[i]-x[i-1] ):(min(dp[cnt][i][j][1]+x[i]-x[i-1], dp[cnt+1][i-1][j][1] ) );
                }
                else{
                    dp[cnt][i-1][j][1]=(dp[cnt][i-1][j][1]==0)?(dp[cnt][i][j][1]+x[i]-x[i-1] ):(min(dp[cnt][i-1][j][1], dp[cnt][i][j][1]+x[i]-x[i-1]) );
                }
            }


            //cout<<"cnt="<<cnt<<" i="<<i<<" j="<<j<<" dp0="<<dp[cnt][i][j][0]<<" dp1="<<dp[cnt][i][j][1]<<"\n";
        }
    }
}
cout<<res;







return 0;
}

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