Submission #915049

#	Time	Username	Problem	Language	Result	Execution time	Memory
915049		happypotato	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	93 ms	132532 KiB

ho_t3

#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';
}

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