Submission #1256576

#TimeUsernameProblemLanguageResultExecution timeMemory
1256576namhhCollecting Stamps 3 (JOI20_ho_t3)C++20
0 / 100
1 ms1096 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
const int N = 2e2+5;
int n,len,a[N],t[N],dp[N][N][N][2];
//ga qua phai doc sol huhu :<
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> len;
	for(int i = 1; i <= n; i++) cin >> a[i];
	a[0] = 0;
	a[n+1] = len;
	for(int i = 1; i <= n; i++) cin >> t[i];
	for(int i = 0; i <= n+1; i++){
		for(int j = 0; j <= n+1; j++){
			for(int k = 0; k <= n+1; k++){
				for(int l = 0; l <= 1; l++) dp[i][j][k][l] = 1e18;
			}
		}
	}
	int ans = 0;
	dp[0][n+1][0][0] = dp[0][n+1][0][1] = 0;
	for(int k = 0; k <= n; k++){
		for(int i = 0; i < n; i++){
			for(int j = n+1; j > i; j--){
				for(int l = 0; l <= 1; l++){
					if(dp[i][j][k][l] > 1e12) continue;
					if(l == 0){
						int x = dp[i][j][k][l]+a[i+1]-a[i];
						if(x > t[i+1]) dp[i+1][j][k][0] = min(dp[i+1][j][k][0],x);
						else dp[i+1][j][k+1][0] = min(dp[i+1][j][k+1][0],x);
						int y = dp[i][j][k][l]+len-a[j-1]+a[i];
						if(y > t[j-1]) dp[i][j-1][k][1] = min(dp[i][j-1][k][1],y);
						else dp[i][j-1][k+1][1] = min(dp[i][j-1][k+1][1],y);
					}
					else{
						int x = dp[i][j][k][l]+len-a[j]+a[i+1];
						if(x > t[i+1]) dp[i+1][j][k][0] = min(dp[i+1][j][k][0],x);
						else dp[i+1][j][k+1][0] = min(dp[i+1][j][k+1][0],x);
						int y = dp[i][j][k][l]+a[j]-a[j-1];
						if(y > t[j-1]) dp[i][j-1][k][1] = min(dp[i][j-1][k][1],y);
						else dp[i][j-1][k+1][1] = min(dp[i][j-1][k+1][1],y);
					}
				}
			}
		}
	}
	for(int k = n; k >= 0; k--){
		for(int i = 0; i <= n; i++){
			for(int j = n+1; j >= i; j--){
				for(int l = 0; l <= 1; l++){
					if(dp[i][j][k][l] < 1e12){
						cout << k;
						return 0;
					}
				}
			}
		}
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...