Submission #669642

#TimeUsernameProblemLanguageResultExecution timeMemory
669642Darren0724Collecting Stamps 3 (JOI20_ho_t3)C++17
100 / 100
687 ms456064 KiB
//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;
}


#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...