제출 #1256560

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1256560		namhh	Collecting Stamps 3 (JOI20_ho_t3)	C++20	0 / 100	0 ms	724 KiB

ho_t3

#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] = 1e9+1;
			}
		}
	}
	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] > 1e9) 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][0] = min(dp[i][j-1][k][0],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][0] = min(dp[i][j-1][k][0],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] < 1e9){
						cout << k;
						return 0;
					}
				}
			}
		}
	}
}

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