Submission #669642

#	Time	Username	Problem	Language	Result	Execution time	Memory
669642		Darren0724	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	687 ms	456064 KiB

ho_t3

//challenge: 100
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define v vector
int n,L;
vector<int> x,t;
v<v<v<v<int>>>> dp;
const int INF=1e18;
int dis(int a,int b){
    return min(abs(x[a]-x[b]),L-abs(x[a]-x[b]));
}
int f(int l,int r,int cnt,int s){
    if(cnt==0){
        return INF;
    }
    if(r-l+1<cnt){
        return -INF;
    }
    if(dp[l][r][cnt][s]!=-INF){
        return dp[l][r][cnt][s];
    }

    int now=0;
    if(s==0){
        now=l-1;
    }
    else{
        now=r+1;
    }
    dp[l][r][cnt][s]=max(dp[l][r][cnt][s],f(l+1,r,cnt,0)-dis(now,l));
    dp[l][r][cnt][s]=max(dp[l][r][cnt][s],f(l,r-1,cnt,1)-dis(now,r));
    dp[l][r][cnt][s]=max(dp[l][r][cnt][s],min(f(l+1,r,cnt-1,0),t[l])-dis(now,l));
    dp[l][r][cnt][s]=max(dp[l][r][cnt][s],min(f(l,r-1,cnt-1,1),t[r])-dis(now,r));
    return dp[l][r][cnt][s];
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>L;
    t.resize(n+2);
    x.resize(n+2);
    for(int i=1;i<=n;i++){
        cin>>x[i];
    }
    for(int i=1;i<=n;i++){
        cin>>t[i];
    }
    dp.resize(n+2,v<v<v<int>>>(n+2,v<v<int>>(n+2,v<int>(2,-INF))));
    int ans=0;
    for(int i=1;i<=n;i++){
        if(f(1,n,i,0)>=0){
            ans=i;
        }
    }
    cout<<ans<<endl;



    return 0;
}

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