Submission #1151370

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151370		h1euct	Collecting Stamps 3 (JOI20_ho_t3)	C++20	100 / 100	106 ms	132204 KiB

ho_t3

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

#define fi first
#define se second

#define int long long

const int MX = 200 + 5;
const int MOD = 1e9 + 7;

int n, l;
int x[MX], t[MX];
int dp[MX][MX][MX][2];

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	// int test; cin>>test; while (test--) {}	
	cin >> n >> l;
	for (int i = 1; i <= n; i++) cin >> x[i];
	for (int i = 1; i <= n; i++) cin >> t[i];
	for (int i = 0; i <= 201; i++) {
		for (int j = 0; j <= 201; j++) {
			for (int k = 0; k <= 201; k++) {
				dp[i][j][k][0] = 1e18;
				dp[i][j][k][1] = 1e18;
			}
		}
	}
	x[n + 1] = l;
	dp[0][n + 1][0][0] = 0;
	dp[0][n + 1][0][1] = 0;
	// dp[l][r][score][0 / 1 left or right]
	for (int i = 0; i <= n; i++) { // l
		for (int j = n + 1; j > i; j--) { // r
			if (i == 0 && j == n + 1) continue;
			for (int k = 0; k <= n; k++) { // score
				if (i >= 1) {
					dp[i][j][k][0] = min(dp[i][j][k][0], dp[i - 1][j][k][0] + (x[i] - x[i - 1]));
					if (k >= 1 && dp[i - 1][j][k - 1][0] + (x[i] - x[i - 1]) <= t[i]) {
						dp[i][j][k][0] = min(dp[i][j][k][0], dp[i - 1][j][k - 1][0] + (x[i] - x[i - 1]));
					}
					dp[i][j][k][0] = min(dp[i][j][k][0], dp[i - 1][j][k][1] + (x[i] + l - x[j]));
					if (k >= 1 && dp[i - 1][j][k - 1][1] + (x[i] + l - x[j]) <= t[i]) {
						dp[i][j][k][0] = min(dp[i][j][k][0], dp[i - 1][j][k - 1][1] + (x[i] + l - x[j]));
					}
				}
				if (j <= n) {
					dp[i][j][k][1] = min(dp[i][j][k][1], dp[i][j + 1][k][1] + (x[j + 1] - x[j]));
					if (k >= 1 && dp[i][j + 1][k - 1][1] + (x[j + 1] - x[j]) <= t[j]) {
						dp[i][j][k][1] = min(dp[i][j][k][1], dp[i][j + 1][k - 1][1] + (x[j + 1] - x[j]));
					}
					dp[i][j][k][1] = min(dp[i][j][k][1], dp[i][j + 1][k][0] + (l - x[j] + x[i]));
					if (k >= 1 && dp[i][j + 1][k - 1][0] + (l - x[j] + x[i]) <= t[j]) {
						dp[i][j][k][1] = min(dp[i][j][k][1], dp[i][j + 1][k - 1][0] + (l - x[j] + x[i]));
					}
				}
			}
		}
	}
	int fn = 0;
	for (int i = 0; i <= n; i++) {
		for (int j = n + 1; j > i; j--) {
			if (i == 0 && j == n + 1) continue;
			for (int k = 0; k <= n; k++) {
				if (dp[i][j][k][0] != 1e18 || dp[i][j][k][1] != 1e18) fn = max(fn, k);
			} 
		}
	}
	cout << fn;
	return 0;
}
// binhtinhtutinkhongcaycunhungmotkhikhongcontutinnualatuyetvong

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