Submission #997580

#	Time	Username	Problem	Language	Result	Execution time	Memory
997580		irmuun	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	56 ms	134320 KiB

ho_t3

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

//try
template<class T> T &chmax(T &a,const T &b){ return a = max(a,b); }
template<class T> T &chmin(T &a,const T &b){ return a = min(a,b); }

ll dpL[205][205][205];
ll dpR[205][205][205];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n,L;
    cin>>n>>L;
    ll x[n+5],t[n+5];
    x[0]=0;
    x[n+1]=L;
    for(ll i=1;i<=n;i++){
        cin>>x[i];
    }
    for(ll i=1;i<=n;i++){
        cin>>t[i];
    }
    for(ll i=0;i<=n+1;i++){
        for(ll j=0;j<=n+1;j++){
            for(ll k=0;k<=n;k++){
                dpL[i][j][k]=1e18;
                dpR[i][j][k]=1e18;
            }
        }
    }
    dpL[0][n+1][0]=0;
    dpR[0][n+1][0]=0;
    for(ll i=0;i<=n;i++){
        for(ll j=n+1;j>=i+2;j--){
            for(ll k=0;k<=n;k++){
                ll tm=min(dpL[i][j][k]+x[i+1]-x[i],dpR[i][j][k]+L-(x[j]-x[i+1]));
                chmin(dpL[i+1][j][k+(tm<=t[i+1])],tm);
                tm=min(dpR[i][j][k]+x[j]-x[j-1],dpL[i][j][k]+L-(x[j-1]-x[i]));
                chmin(dpR[i][j-1][k+(tm<=t[j-1])],tm);
            }
        }
    }
    ll ans=0;
    for(ll i=0;i<=n+1;i++){
        for(ll j=0;j<=n+1;j++){
            for(ll k=0;k<=n;k++){
                if(dpL[i][j][k]!=1e18){
                    ans=max(ans,k);
                }
                if(dpR[i][j][k]!=1e18){
                    ans=max(ans,k);
                }
            }
        }
    }
    cout<<ans;
}

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