Submission #211111

#	Time	Username	Problem	Language	Result	Execution time	Memory
211111		kshitij_sodani	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	166 ms	130172 KiB

ho_t3

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef  long long int llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
llo t[201];
llo it[201];
llo n,l;
llo ma=0;

llo dp[201][201][205][2];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>l;
	memset(dp,-1,sizeof(dp));
 	for(int i=0;i<201;i++){
 		for(int j=0;j<201;j++){
 			for(int k=0;k<205;k++){
 				dp[i][j][k][0]=-1;
 				dp[i][j][k][1]=-1;
 			}
 		}
 	}
	for(llo i=0;i<n;i++){
		cin>>it[i];
	}
	for(llo i=0;i<n;i++){
		cin>>t[i];
	}
 
	for(llo i=0;i<n;i++){
		llo dis=min(it[i],l-it[i]);
		llo val=0;
		if(dis<=t[i]){
			val=1;
		}
		dp[i][i][val][0]=dis;
		dp[i][i][val][1]=dis;
	}
 
	for(llo ii=1;ii<n;ii++){
		for(llo j=0;j<n;j++){
			llo i=(j+ii)%n;
			for(llo k=0;k<n+1;k++){
				if(dp[j][(i-1+n)%n][k][1]>-1){
					llo tt=dp[j][(i-1+n)%n][k][1]+min(abs(it[i]-it[(i-1+n)%n]),l-abs(it[i]-it[(i-1+n)%n]));
					if(tt<=t[i]){
						if(dp[j][i][k+1][1]==-1){
							dp[j][i][k+1][1]=tt;
						}
						dp[j][i][k+1][1]=min(dp[j][i][k+1][1],tt);
					}
					if(dp[j][i][k][1]==-1){
						dp[j][i][k][1]=tt;
					}
					dp[j][i][k][1]=min(dp[j][i][k][1],tt);
				}	
				if(dp[j][(i-1+n)%n][k][0]>-1){
					llo tt=dp[j][(i-1+n)%n][k][0]+min(abs(it[i]-it[j]),l-abs(it[i]-it[j]));
					if(tt<=t[i]){
						if(dp[j][i][k+1][1]==-1){
							dp[j][i][k+1][1]=tt;
						}
						dp[j][i][k+1][1]=min(dp[j][i][k+1][1],tt);
					}
					if(dp[j][i][k][1]==-1){
						dp[j][i][k][1]=tt;
					}
					dp[j][i][k][1]=min(dp[j][i][k][1],tt);
				}	
				
				
				if(dp[(j+1)%n][i][k][0]>-1){
					llo tt=dp[(j+1)%n][i][k][0]+min(abs(it[j]-it[(j+1)%n]),l-abs(it[j]-it[(j+1)%n]));
					if(tt<=t[j]){
						if(dp[j][i][k+1][0]==-1){
							dp[j][i][k+1][0]=tt;
						}
						dp[j][i][k+1][0]=min(dp[j][i][k+1][0],tt);
					}
					if(dp[j][i][k][0]==-1){
						dp[j][i][k][0]=tt;
					}
					dp[j][i][k][0]=min(dp[j][i][k][0],tt);
				}	
				if(dp[(j+1)%n][i][k][1]>-1){
					llo tt=dp[(j+1)%n][i][k][1]+min(abs(it[j]-it[i]),l-abs(it[j]-it[i]));
					if(tt<=t[j]){
						if(dp[j][i][k+1][0]==-1){
							dp[j][i][k+1][0]=tt;
						}
						dp[j][i][k+1][0]=min(dp[j][i][k+1][0],tt);
					}
					if(dp[j][i][k][0]==-1){
						dp[j][i][k][0]=tt;
					}
					dp[j][i][k][0]=min(dp[j][i][k][0],tt);
				}	
			}
		}
	}
	llo ans=0;
	for(llo i=0;i<n;i++){
		for(llo j=0;j<n;j++){
			for(llo k=0;k<n+1;k++){
				if(dp[i][j][k][0]!=-1){
					ans=max(ans,k);
				}
				if(dp[i][j][k][1]!=-1){
					ans=max(ans,k);
				}

			}
		}
	}
	cout<<ans<<endl;
 
 
	return 0;
	
}

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