Submission #1185147

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185147		user736482	Collecting Stamps 3 (JOI20_ho_t3)	C++20	100 / 100	138 ms	140616 KiB

ho_t3

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define INFL 1000000000000000099LL
#define MAXN 207

ll a,b,c,t,n,k,k2,k3,k4,ans,l;
vector<pair<ll,ll>>v;//gdzie,kiedy
string s;

ll bst[MAXN+7][MAXN+7][MAXN+7][2];//skad,ile,jakiwyn

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>l;
    v.pb({0,-INFL});
    for(ll i=0;i<n;i++){
        cin>>a;
        v.pb({a,0});
    }
    for(ll i=0;i<n;i++){
        cin>>a;
        v[i+1].ss=a;
    }
   // n++;
    
    for(ll i=0;i<n+1;i++)
        v.pb({v[i].ff+l,v[i].ss});
    for(ll i=0;i<3*MAXN;i++)
        v.pb({INFL,-INFL});
    for(ll i=0;i<=n+3;i++){
        for(ll j=0;j<=n+3;j++){
            for(ll k=0;k<=n+3;k++){
                bst[i][j][k][0]=INFL;bst[i][j][k][1]=INFL;
                //cout<<i<<" "<<j<<" "<<k<<"\n"<<flush;
            }
        }
    }//return 0;
    //for(ll i=0;i<2*n+3;i++)cout<<v[i].ff<<" "<<v[i].ss<<"\n";
    //cout<<"\n\n";
    bst[n+1][0][0][0]=0;
    bst[n+1][0][0][1]=0;
    //return 0;
    for(ll i=0;i<=n;i++){
        for(ll j=2;j<=n+1;j++){
            for(ll k=0;k<=n;k++){
                if(bst[j][i][k][0]+v[j].ff-v[j-1].ff<=v[j-1].ss){
                    //cout<<"xd";
                    bst[j-1][i+1][k+1][0]=min(bst[j-1][i+1][k+1][0],bst[j][i][k][0]+v[j].ff-v[j-1].ff);
                    bst[j-1][i+1][k+1][1]=min(bst[j-1][i+1][k+1][1],bst[j-1][i+1][k+1][0]+v[j+i].ff-v[j-1].ff);
                }
                else{
                    bst[j-1][i+1][k][0]=min(bst[j-1][i+1][k][0],bst[j][i][k][0]+v[j].ff-v[j-1].ff);
                    bst[j-1][i+1][k][1]=min(bst[j-1][i+1][k][1],bst[j-1][i+1][k][0]+v[j+i].ff-v[j-1].ff);
               
                }
               // if(bst[6][1][1][1]!=INFL)
                //cout<<j<<" "<<i<<" "<<k<<" "<<bst[6][1][1][1]<<" ";
                if(bst[j][i][k][1]+v[j+i+1].ff-v[j+i].ff<=v[j+i+1].ss){
                    bst[j][i+1][k+1][1]=min(bst[j][i+1][k+1][1],bst[j][i][k][1]+v[j+i+1].ff-v[j+i].ff);
                    bst[j][i+1][k+1][0]=min(bst[j][i+1][k+1][0],bst[j][i+1][k+1][1]+v[j+i+1].ff-v[j].ff);
                
                }
                else{
                    bst[j][i+1][k][1]=min(bst[j][i+1][k][1],bst[j][i][k][1]+v[j+i+1].ff-v[j+i].ff);
                    bst[j][i+1][k][0]=min(bst[j][i+1][k][0],bst[j][i+1][k][1]+v[j+i+1].ff-v[j].ff);
                
                }
                //if(bst[6][1][1][1]!=INFL)
                //cout<<j<<" "<<i<<" "<<k<<" "<<bst[6][1][1][1]<<" ";
            }
        }
    }
    for(ll i=0;i<=n;i++){
        for(ll j=1;j<=n+1;j++){
            for(ll k=0;k<=n;k++){
                //cout<<j<<" "<<i<<" "<<k<<" "<<bst[j][i][k][0]<<" "<<bst[j][i][k][1]<<"\n";
                if(bst[j][i][k][0]<INFL || bst[j][i][k][1]<INFL){
                    ans=max(ans,k);
                }
            }
        }
    }
    cout<<ans;
    return 0;
}

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