Submission #915049

#TimeUsernameProblemLanguageResultExecution timeMemory
915049happypotatoCollecting Stamps 3 (JOI20_ho_t3)C++17
100 / 100
93 ms132532 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAX = 1e18;
const int mxN = 205;
int dp[mxN][mxN][mxN][2];
void chmin(int &x, int y) {
	x = min(x, y);
}
int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n, l;
	cin >> n >> l;
	int x[n + 2], t[n + 1];
	x[0] = 0; x[n + 1] = l;
	for (int i = 1; i <= n; i++) cin >> x[i];
	for (int i = 0; i <= n + 1; i++) {
		for (int j = 0; j <= n + 1; j++) {
			for (int k = 0; k <= n; k++) {
				dp[i][j][k][0] = dp[i][j][k][1] = MAX;
			}
		}
	}
	for (int i = 1; i <= n; i++) cin >> t[i];
	dp[0][n + 1][0][0] = dp[0][n + 1][0][1] = 0;
	int ans = 0;
	for (int i = 0; i <= n; i++) {
		for (int j = n + 1; j > i; j--) {
			if (i == 0 && j == n + 1) continue;
			int dist;
			for (int k = 0; k <= n; k++) {
				if (i >= 1) {
					dist = x[i] - x[i - 1];
					chmin(dp[i][j][k][0], dp[i - 1][j][k][0] + dist);
					if (k && dp[i - 1][j][k - 1][0] + dist <= t[i]) {
						chmin(dp[i][j][k][0], dp[i - 1][j][k - 1][0] + dist);
					}

					dist = (l - x[j]) + x[i];
					chmin(dp[i][j][k][0], dp[i - 1][j][k][1] + dist);
					if (k && dp[i - 1][j][k - 1][1] + dist <= t[i]) {
						chmin(dp[i][j][k][0], dp[i - 1][j][k - 1][1] + dist);
					}
				}
				if (j <= n) {
					dist = x[i] + (l - x[j]);
					chmin(dp[i][j][k][1], dp[i][j + 1][k][0] + dist);
					if (k && dp[i][j + 1][k - 1][0] + dist <= t[j]) {
						chmin(dp[i][j][k][1], dp[i][j + 1][k - 1][0] + dist);
					}

					dist = x[j + 1] - x[j];
					chmin(dp[i][j][k][1], dp[i][j + 1][k][1] + dist);
					if (k && dp[i][j + 1][k - 1][1] + dist <= t[j]) {
						chmin(dp[i][j][k][1], dp[i][j + 1][k - 1][1] + dist);
					}
				}

				// cerr << i << ' ' << j << ' ' << k << ": ";
				// cerr << dp[i][j][k][0] << ' ' << dp[i][j][k][1] << endl;
				if (min(dp[i][j][k][0], dp[i][j][k][1]) < MAX) ans = max(ans, k);
			}
		}
	}
	cout << ans << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...