제출 #1109994

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1109994		DobromirAngelov	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	35 ms	66896 KiB

ho_t3

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;

const int MAXN=205;
const int INF=1e9+5;

int n,L;
int x[MAXN];
int t[MAXN];
int dp[MAXN][MAXN][MAXN][2];

int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

cin>>n>>L;
for(int i=1;i<=n;i++) cin>>x[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 s=1;s<=n;s++)
{
    for(int i=0;i<=s;i++)
    {
        int j=n-(s-i)+1;
        for(int cnt=0;cnt<=s;cnt++)
        {
            if(i>0)
            {
                int time=dp[i-1][j][cnt][0];
                int add=abs(x[i-1]-x[i]); add=min(add, L-add);
                if(time+add<=t[i]) dp[i][j][cnt+1][0]=min(dp[i][j][cnt+1][0], time+add);
                else dp[i][j][cnt][0]=min(dp[i][j][cnt][0], time+add);

                time=dp[i-1][j][cnt][1];
                add=abs(x[i]-x[j]); add=min(add, L-add);
                if(time+add<=t[i]) dp[i][j][cnt+1][0]=min(dp[i][j][cnt+1][0], time+add);
                else dp[i][j][cnt][0]=min(dp[i][j][cnt][0], time+add);
            }
            if(j<n+1)
            {
                int time=dp[i][j+1][cnt][0];
                int add=abs(x[j]-x[i]); add=min(add, L-add);
                if(time+add<=t[j]) dp[i][j][cnt+1][1]=min(dp[i][j][cnt+1][1], time+add);
                else dp[i][j][cnt][1]=min(dp[i][j][cnt][1], time+add);

                time=dp[i][j+1][cnt][1];
                add=abs(x[j]-x[j+1]); add=min(add, L-add);
                if(time+add<=t[j]) dp[i][j][cnt+1][1]=min(dp[i][j][cnt+1][1], time+add);
                else dp[i][j][cnt][1]=min(dp[i][j][cnt][1], time+add);
            }
            if(dp[i][j][cnt][0]<INF || dp[i][j][cnt][1]<INF) ans=max(ans, cnt);
        }
    }
}

cout<<ans<<endl;

return 0;
}

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