Submission #1154932

#TimeUsernameProblemLanguageResultExecution timeMemory
1154932elotelo966Collecting Stamps 3 (JOI20_ho_t3)C++20
100 / 100
109 ms130920 KiB
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define FOR for(int i=1;i<=n;i++)
#define lim 205
#define DP dp[i][j][k][l]

int n,l;

int x[lim],t[lim];

int dp[lim][lim][lim][2];

//0 sol

//1 sag

int32_t main(){
	faster
	cin>>n>>l;
	FOR{
		cin>>x[i];
	}
	
	x[n+1]=l;
	
	FOR{
		cin>>t[i];
	}
	
	for(int i=0;i<=n;i++){
		for(int j=0;j<=n;j++){
			for(int k=0;k<=n;k++){
				for(int l=0;l<=1;l++)DP=LLONG_MAX;
			}
		}
	}
	
	dp[0][0][0][0]=dp[0][0][0][1]=0;
	
	for(int i=0;i<=n;i++){
		for(int j=0;j<=n-i;j++){
			for(int k=0;k<=i+j;k++){
				//soldan
				int zaman=x[i+1]-x[i]+dp[i][j][k][0];
				if(dp[i][j][k][0]==LLONG_MAX)zaman=LLONG_MAX;
				int ol=0;
				if(zaman<=t[i+1])ol=1;
				dp[i+1][j][k+ol][0]=min(dp[i+1][j][k+ol][0],zaman);
				
				zaman=x[i]+l-x[n-j]+dp[i][j][k][0];
				if(dp[i][j][k][0]==LLONG_MAX)zaman=LLONG_MAX;
				ol=0;
				if(zaman<=t[n-j])ol=1;
				dp[i][j+1][k+ol][1]=min(dp[i][j+1][k+ol][1],zaman);
				
				// sagdan
				zaman=x[n-(j-1)]-x[n-j]+dp[i][j][k][1];
				if(dp[i][j][k][1]==LLONG_MAX)zaman=LLONG_MAX;
				ol=0;
				if(zaman<=t[n-j])ol=1;
				dp[i][j+1][k+ol][1]=min(dp[i][j+1][k+ol][1],zaman);
				
				zaman=l-x[n-(j-1)]+x[i+1]+dp[i][j][k][1];
				if(dp[i][j][k][1]==LLONG_MAX)zaman=LLONG_MAX;
				ol=0;
				if(zaman<=t[i+1])ol=1;
				dp[i+1][j][k+ol][0]=min(dp[i+1][j][k+ol][0],zaman);
			}
		}
	}
	
	int cev=0;
	
	for(int i=0;i<=n;i++){
		for(int j=0;j<=n;j++){
			for(int k=0;k<=n;k++){
				for(int l=0;l<=1;l++){
					//cout<<DP<<" "<<i<<" "<<j<<" "<<k<<" "<<l<<endl;
					if(i+j==n && DP!=LLONG_MAX)cev=max(cev,k);
				}
			}
		}
	}
	
	cout<<cev<<'\n';
	
	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...