Submission #1154826

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154826		elotelo966	Collecting Stamps 3 (JOI20_ho_t3)	C++20	0 / 100	0 ms	576 KiB

ho_t3

#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<=n;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]+25-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=25-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++){
					if(DP!=LLONG_MAX)cev=max(cev,k);
				}
			}
		}
	}
	
	cout<<cev<<'\n';
	
	return 0;
}

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