Submission #211060

#	Time	Username	Problem	Language	Result	Execution time	Memory
211060		kshitij_sodani	Collecting Stamps 3 (JOI20_ho_t3)	C++17	0 / 100	81 ms	130168 KiB

ho_t3

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef  long long 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;
void find(llo i=0,llo j=0,llo loc=0,llo co=0,llo la=0){
	j=(j+n)%n;

	if(loc<=t[la]){
		co+=1;
	}
	if(i+1==j or (j==0 and i==n-1)){
		ma=max(ma,co);
		//cout<<loc<<" "<<la<<endl;
	}
	else{
		find((i+1)%n,j,loc+min(abs(it[la]-it[(i+1)%n]),l-abs(it[la]-it[(i+1)%n])),co,(i+1)%n);
		find(i,(j-1+n)%n,loc+min(abs(it[la]-it[(j-1+n)%n]),l-abs(it[la]-it[(j-1+n)%n])),co,(j-1+n)%n);
	}

}
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(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[(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+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[(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);
				}	
			}
		}
	}
	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){
					ma=max(ma,k);
				}
				if(dp[i][j][k][1]!=-1){
					ma=max(ma,k);
				}
			/*	ans=max(ans,dp[i][j][k][0]);
				ans=max(ans,dp[i][j][k][1]);*/
			}
		}
	}
	cout<<ma<<endl;


	return 0;
	
}

Compilation message (stderr)

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:116:6: warning: unused variable 'ans' [-Wunused-variable]
  llo ans=0;
      ^~~

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