제출 #1275573

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275573		kaiboy	Collecting Stamps 3 (JOI20_ho_t3)	C++20	100 / 100	34 ms	33908 KiB

ho_t3

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

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