Submission #916337

#	Time	Username	Problem	Language	Result	Execution time	Memory
916337		EJIC_B_KEDAX	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	102 ms	66756 KiB

ho_t3

#include <bits/stdc++.h>

#define x first
#define y second

using ll = long long;
#define int ll

using namespace std;

int32_t main() {
	int n, L;
	cin >> n >> L;
	vector<pair<int, int>> a(n + 2);
	a[0] = {0, INT64_MAX};
	a[n + 1] = {L, INT64_MAX};
	for (int i = 1; i <= n; i++) {
		cin >> a[i].x;
	}
	for (int i = 1; i <= n; i++) {
		cin >> a[i].y;
	}
	n += 2;
	vector<vector<vector<ll>>> dp(n, vector<vector<ll>>(n, vector<ll>(n, INT64_MAX / 2)));
	dp[0][n - 1][0] = 0;
	for (int l = n - 1; l > 1; l--) {
		for (int i = 0; i + l < n; i++) {
			int j = i + l;
			for (int s = 0; s < n; s++) {
				ll dist1 = a[i + 1].x - a[i].x, dist2 = a[i].x + L - a[j - 1].x;
				if (dp[i][j][s] + dist1 <= a[i + 1].y) {
					dp[i + 1][j][s + 1] = min(dp[i + 1][j][s + 1], dp[i][j][s] + dist1);
				} else {
					dp[i + 1][j][s] = min(dp[i + 1][j][s], dp[i][j][s] + dist1);
				}
				if (dp[i][j][s] + dist2 <= a[j - 1].y) {
					dp[j - 1][i][s + 1] = min(dp[j - 1][i][s + 1], dp[i][j][s] + dist2);
				} else {
					dp[j - 1][i][s] = min(dp[j - 1][i][s], dp[i][j][s] + dist2);
				}
			}
		}
		for (int i = l; i < n; i++) {
			int j = i - l;
			for (int s = 0; s < n; s++) {
				ll dist1 = a[i].x - a[i - 1].x, dist2 = L - a[i].x + a[j + 1].x;
				if (dp[i][j][s] + dist1 <= a[i - 1].y) {
					dp[i - 1][j][s + 1] = min(dp[i - 1][j][s + 1], dp[i][j][s] + dist1);
				} else {
					dp[i - 1][j][s] = min(dp[i - 1][j][s], dp[i][j][s] + dist1);
				}
				if (dp[i][j][s] + dist2 <= a[j + 1].y) {
					dp[j + 1][i][s + 1] = min(dp[j + 1][i][s + 1], dp[i][j][s] + dist2);
				} else {
					dp[j + 1][i][s] = min(dp[j + 1][i][s], dp[i][j][s] + dist2);
				}
			}
		}
	}
	for (int s = n - 1; s >= 0; s--) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (dp[i][j][s] < INT64_MAX / 2) {
					cout << s << '\n';
					return 0;
				}
			}
		}
	}
}

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