Submission #1275573

#TimeUsernameProblemLanguageResultExecution timeMemory
1275573kaiboyCollecting Stamps 3 (JOI20_ho_t3)C++20
100 / 100
34 ms33908 KiB
#include <algorithm>
#include <iostream>

using namespace std;

const int   N = 200;
const int INF = 0x3f3f3f3f;

int aa[N], tt[N], dp[N + 1][N + 1][N + 1], dq[N + 1][N + 1][N + 1];

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n, a_; cin >> n >> a_;
	for (int i = 0; i < n; i++)
		cin >> aa[i];
	for (int i = 0; i < n; i++)
		cin >> tt[i];
	for (int l = 0; l <= n; l++)
		for (int r = 0; l + r <= n; r++)
			for (int k = 0; k <= n; k++)
				dp[l][r][k] = dq[l][r][k] = INF;
	dp[0][0][0] = dq[0][0][0] = 0;
	for (int l = 0; l < n; l++)
		for (int r = 0; l + r < n; r++)
			for (int k = 0; k < n; k++) {
				dq[l][r][k] = min(dq[l][r][k], dp[l][r][k] + (l ? aa[l - 1] : 0) + (r ? a_ - aa[n - r] : 0));
				dp[l][r][k] = min(dp[l][r][k], dq[l][r][k] + (l ? aa[l - 1] : 0) + (r ? a_ - aa[n - r] : 0));
				int t = dp[l][r][k] + aa[l] - (l ? aa[l - 1] : 0), k_ = k + (t <= tt[l]);
				dp[l + 1][r][k_] = min(dp[l + 1][r][k_], t);
				t = dq[l][r][k] + (r ? aa[n - r] : a_) - aa[n - 1 - r], k_ = k + (t <= tt[n - 1 - r]);
				dq[l][r + 1][k_] = min(dq[l][r + 1][k_], t);
			}
	int ans = 0;
	for (int l = 0; l <= n; l++)
		for (int r = 0; l + r <= n; r++)
			for (int k = 0; k <= n; k++)
				if (dp[l][r][k] < INF || dq[l][r][k] < INF)
					ans = max(ans, k);
	cout << ans << '\n';
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...