Submission #890582

#	Time	Username	Problem	Language	Result	Execution time	Memory
890582		ParsaS	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	46 ms	135512 KiB

ho_t3

// In the name of God
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
const int N = 200 + 5;
int n, L, X[N], T[N];
ll dp[N][N][N][2];

void solve() {
	cin >> n >> L;
	for (int i = 1; i <= n; i++)
		cin >> X[i];
	for (int i = 1; i <= n; i++)
		cin >> T[i];
	memset(dp, 63, sizeof dp);
	X[n + 1] = L;
	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--) {
			for (int k = 0; k <= n; k++) {
				if (i == 0 && j == n + 1 && k == 0)
					continue;
				ll x = 1e17;
				if (i) {
					x = dp[i - 1][j][k][0] + X[i] - X[i - 1];
					if (dp[i - 1][j][k - 1][0] + X[i] - X[i - 1] <= T[i]) {
						x = min(x, dp[i - 1][j][k - 1][0] + X[i] - X[i - 1]);
					}
					x = min(x, dp[i - 1][j][k][1] + X[i] + L - X[j]);
					if (dp[i - 1][j][k - 1][1] + X[i] + L - X[j] <= T[i]) {
						x = min(x, dp[i - 1][j][k - 1][1] + X[i] + L - X[j]);
					}
				}
				if (x < 1e17)
					ans = max(ans, k);
				dp[i][j][k][0] = x;
				x = 1e17;
				if (j < n + 1) {
					x = dp[i][j + 1][k][1] + X[j + 1] - X[j];
					if (dp[i][j + 1][k - 1][1] + X[j + 1] - X[j] <= T[j])
						x = min(x, dp[i][j + 1][k - 1][1] + X[j + 1] - X[j]);
					x = min(x, dp[i][j + 1][k][0] + X[i] + L - X[j]);
					if (dp[i][j + 1][k - 1][0] + X[i] + L - X[j] <= T[j])
						x = min(x, dp[i][j + 1][k - 1][0] + X[i] + L - X[j]);
				}
				if (x < 1e17)
					ans = max(ans, k);
				dp[i][j][k][1] = x;
			}
		}
	}
	cout << ans << endl;
}	

int32_t main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int tc = 1; // cin >> tc;
	while (tc--) {
		solve();
	}

	return 0;
}

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