Submission #222543

#	Time	Username	Problem	Language	Result	Execution time	Memory
222543		astoria	Collecting Stamps 3 (JOI20_ho_t3)	C++14	0 / 100	5 ms	384 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main(){
	int n,l;
	cin>>n>>l;
	int x[n+5],t[n+5];
	for(int i=1; i<=n; i++) cin>>x[i];
	for(int i=1; i<=n; i++) cin>>t[i];
	x[n+1] = l;
	
	int dp[n+5][n+5][n+5][2];
	for(int i=0; i<n+5; i++){
		for(int j=0; j<n+5; j++){
			for(int k=0; k<n+5; k++){
				dp[i][j][k][0]=1e17; dp[i][j][k][1]=1e17;
			}
		}
	} //fill
	
	dp[0][n+1][0][0] = 0;
	dp[0][n+1][0][1] = 0;
	
	int at0[n+5];
	
	fill(at0,at0+n+5,1e17);
	at0[0] = 0;
	for(int k=0; k<=n; k++){
		for(int j=n; j>0; j--){
			dp[0][j][k][1] = min(dp[0][j+1][k][1] + (x[j+1]-x[j]), dp[0][j][k][1]);
			if(k!=0){
				if(dp[0][j+1][k-1][1] + (x[j+1]-x[j]) <= t[j]){
					dp[0][j][k][1] = min(dp[0][j+1][k-1][1] + (x[j+1]-x[j]), dp[0][j][k][1]);
				}
				if(at0[k-1] + l-x[j] <= t[j]){
					dp[0][j][k][1] = min(dp[0][j][k][1], at0[k-1] + l-x[j]);
				}
			}
		}
		for(int i=1; i<=n; i++){
			dp[i][n+1][k][0] = min(dp[i-1][n+1][k][0] + (x[i]-x[i-1]), dp[i][n+1][k][0]);
			if(k!=0){
				if(dp[i-1][n+1][k-1][0] + (x[i]-x[i-1]) <= t[i]){
					dp[i][n+1][k][0] = min(dp[i-1][n+1][k-1][0] + (x[i]-x[i-1]), dp[i][n+1][k][0]);
				}
				if(at0[k-1] + x[i] <= t[i]){
					dp[i][n+1][k][0] = min(dp[i][n+1][k][0], at0[k-1] + x[i]);
				}
			}
			for(int j=n; j>i; j--){
				dp[i][j][k][1] = min(dp[i][j+1][k][1] + (x[j+1]-x[j]), dp[i][j][k][1]);
				dp[i][j][k][0] = min(dp[i-1][j][k][0] + (x[i]-x[i-1]), dp[i][j][k][0]);
				if(k!=0){
					if(dp[i][j+1][k-1][1] + (x[j+1]-x[j]) <= t[j]){
						dp[i][j][k][1] = min(dp[i][j+1][k-1][1] + (x[j+1]-x[j]), dp[i][j][k][1]);
					}
					if(dp[i-1][j][k-1][0] + (x[i]-x[i-1]) <= t[i]){
						dp[i][j][k][0] = min(dp[i-1][j][k-1][0] + (x[i]-x[i-1]), dp[i][j][k][0]);
					}
					if(at0[k-1] + l-x[j] <= t[j]){
						dp[i][j][k][1] = min(dp[i][j][k][1], at0[k-1] + l-x[j]);
					}
					if(at0[k-1] + x[i] <= t[i]){
						dp[i][j][k][0] = min(dp[i][j][k][0], at0[k-1] + x[i]);
					}
				}
				dp[i][j][k][0] = min(dp[i][j][k][0], at0[k]+x[i]);
				dp[i][j][k][1] = min(dp[i][j][k][1], at0[k]+l-x[j]);
				
				at0[k] = min(at0[k], dp[i][j][k][1] + l-x[j]);
				at0[k] = min(at0[k], dp[i][j][k][0] + x[i]);
			}
		}
		//cout<<at0[k]<<endl;
	}
	
	int an=0;
	for(int i=0; i<=n; i++){
		for(int j=0; j<=n; j++){
			for(int k=1; k<=n; k++){
				if(dp[i][j][k][0]<1e15 || dp[i][j][k][1]<1e15) an=max(an,k);
			}
		}
	}
	cout<<an;
}

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