제출 #1340031

#제출 시각아이디문제언어결과실행 시간메모리
1340031WarinchaiCollecting Stamps 3 (JOI20_ho_t3)C++20
0 / 100
1 ms836 KiB
#include<bits/stdc++.h>
#define int long long
using namespace std;

int pos[205],t[205];
int dp[205][205][205][2];
int inf=1e9+5;
int n,l;

int g(int i,int j){
    if(i==n+1)i=0;
    if(j==n+1)j=0;
    return min(abs(pos[i]-pos[j]),l-abs(pos[i]-pos[j]));
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>l;
    for(int i=1;i<=n;i++)cin>>pos[i];
    for(int i=1;i<=n;i++)cin>>t[i];
    for(int i=0;i<=n+1;i++)for(int j=0;j<=n+1;j++)for(int k=0;k<=n+1;k++)dp[i][j][k][0]=dp[i][j][k][1]=inf;
    dp[0][n+1][0][0]=dp[0][n+1][0][1]=0;
    int ans=0;
    for(int i=0;i<=n;i++)for(int j=n+1;j>=1;j--)for(int k=1;k<=n;k++){
        if(j<=i)continue;
        if(i+n-j+1<k)continue;
        if(i==0&&j==n+1)continue;
        //0
        if(i>0){
            dp[i][j][k][0]=min(dp[i-1][j][k][0]+g(i-1,i),dp[i-1][j][k][1]+g(i,j));
            int tme=min(dp[i-1][j][k-1][0]+g(i-1,i),dp[i-1][j][k-1][1]+g(i,j));
            if(tme<=t[i])dp[i][j][k][0]=min(dp[i][j][k][0],tme);
        }
        //1
        if(j<n+1){
            dp[i][j][k][1]=min(dp[i][j+1][k][0]+g(i,j),dp[i][j+1][k][1]+g(j+1,j));
            int tme=min(dp[i][j+1][k-1][0]+g(i,j),dp[i][j+1][k-1][1]+g(j+1,j));
            if(tme<=t[j])dp[i][j][k][1]=min(dp[i][j][k][1],tme);
        }
        if(min(dp[i][j][k][0],dp[i][j][k][1])<inf){
            ans=max(ans,k);
            //cerr<<"can:"<<i<<' '<<j<<" "<<k<<':'<<dp[i][j][k][0]<<" "<<dp[i][j][k][1]<<"\n";
        }
    }
    cout<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...