Submission #890623

#	Time	Username	Problem	Language	Result	Execution time	Memory
890623		LCJLY	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	118 ms	135436 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl; 
#define show4(x,y) for(auto it:x) cout << it << " "; cout << #y << endl;
typedef pair<int,int>pii;
typedef pair<pii,int>pi2;

int n=0;
int len=0;
int pos[205];
int limit[205];
//int memo[205][205][2][205];

//int dp(int l, int r, bool flag, int cur){
	//if(cur>200) return 0;
	//if(l+1>=r) return 0;
	//if(memo[l][r][flag][cur]!=-1) return memo[l][r][flag][cur];
	//int ans=0;
	
	//int dist=cur;
	//if(!flag) dist+=(pos[l+1]-pos[l]);
	//else dist+=(pos[l+1]+k-pos[r]);
	//ans=max(ans,dp(l+1,r,0,dist)+(dist<=limit[l+1]));
	
	//int dist2=cur;
	//if(flag) dist2+=(pos[r]-pos[r-1]);
	//else dist2+=(pos[l]+k-pos[r-1]);
	//ans=max(ans,dp(l,r-1,1,dist2)+(dist2<=limit[r-1]));
	//return memo[l][r][flag][cur]=ans;
//}

void solve(){	
	cin >> n >> len;

	//memset(memo,-1,sizeof(memo));
	for(int x=1;x<=n;x++) cin >> pos[x];
	for(int x=1;x<=n;x++) cin >> limit[x];
	pos[n+1]=len;
	
	//min amount of time to cover (l,r) such that last is a left/right, visiting k stuff
	int dp[n+5][n+5][n+5][2];
	for(int x=0;x<n+5;x++){
		for(int y=0;y<n+5;y++){
			for(int i=0;i<n+5;i++){
				dp[x][y][i][0]=1e15;
				dp[x][y][i][1]=1e15;
			}
		}
	}
	
	dp[0][n+1][0][0]=0;
	dp[0][n+1][0][1]=0;
	
	for(int l=0;l<=n;l++){
		for(int r=n+1;r>l;r--){
			for(int k=0;k<=n;k++){
				//last is left
				int dist=dp[l][r][k][0];
				//visit lft rgt
				int left=pos[l+1]-pos[l];
				int right=pos[l]+len-pos[r-1];
				
				//no take
				dp[l+1][r][k][0]=min(dp[l+1][r][k][0],dist+left);
				dp[l][r-1][k][1]=min(dp[l][r-1][k][1],dist+right);
				
				//take
				if(dist+left<=limit[l+1]){
					dp[l+1][r][k+1][0]=min(dp[l+1][r][k+1][0],dist+left);
				}
				if(dist+right<=limit[r-1]){
					dp[l][r-1][k+1][1]=min(dp[l][r-1][k+1][1],dist+right);
				}
				

				//last is right
				dist=dp[l][r][k][1];
				left=pos[l+1]+len-pos[r];
				right=pos[r]-pos[r-1];
				
				dp[l+1][r][k][0]=min(dp[l+1][r][k][0],dist+left);
				dp[l][r-1][k][1]=min(dp[l][r-1][k][1],dist+right);
				
				if(dist+left<=limit[l+1]){
					dp[l+1][r][k+1][0]=min(dp[l+1][r][k+1][0],dist+left);
				}
				if(dist+right<=limit[r-1]){
					dp[l][r-1][k+1][1]=min(dp[l][r-1][k+1][1],dist+right);
				}
				
				//show3(l,l,r,r,k,k);
				//show2(left,dp[l][r][k][0],right,dp[l][r][k][1]);
			}
		}
	}
	
	int best=0;
	for(int l=0;l<=n;l++){
		for(int r=l+1;r<=n+1;r++){
			for(int k=0;k<=n;k++){
				if(dp[l][r][k][0]<1e15) best=max(best,k);
				if(dp[l][r][k][1]<1e15) best=max(best,k);
			}
		}
	}
	
	cout << best;
}	

int32_t main(){										
	ios::sync_with_stdio(0);	
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}

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