제출 #1151211

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

ho_t3

#include <bits/stdc++.h>
using namespace std;

const int N = 203;
const long long oo = 1e18;
void mini(long long &X, long long Y) {
	if (X > Y) X = Y;
}

int n, l, x[N], ti[N];
long long dp[N][N][N][2];
void solve(void) {
	cin >> n >> l;
	x[0] = 0; x[n + 1] = l;
	for (int i = 1; i <= n; i++) cin >> x[i];
	for (int i = 1; i <= n; i++) cin >> ti[i];
	
	for (int p = 0; p <= n; p++) {
		for (int s = p + 1; s <= n + 1; s++) {
			for (int score = 0; score <= n; score++) {
				dp[p][s][score][0] = dp[p][s][score][1] = oo;
			}
		}
	}
	dp[0][n + 1][0][0] = dp[0][n + 1][0][1] = 0;
	for (int p = 0; p <= n; p++) {
		for (int s = n + 1; s > p; s--) {
			for (int score = 0; score <= n; score++) {
				int t;
				if (dp[p][s][score][1] < oo) {
					t = 0;
					for (int i = p + 1; i < s; i++) {
						t += 2 * dp[p][s][score][1] + x[i] <= ti[i];
						mini(dp[i][s][score + t][0], dp[p][s][score][1] + x[i]);
					}
				}
				if (dp[p][s][score][0] < oo) {
					t = 0;
					for (int i = s - 1; i > p; i--) {
						t += 2 * dp[p][s][score][0] + l - x[i] <= ti[i];
						mini(dp[p][i][score + t][1], dp[p][s][score][0] + l - x[i]);
					}
				}
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= n + 1; i++) {
		for (int score = n; score; score--) {
			if (min(dp[i - 1][i][score][0], dp[i - 1][i][score][1]) < oo) {
				ans = max(ans, score);
				break;
			}
		}
	}
	cout << ans;
}

signed main(void) {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    int T = 1;// cin >> T; 
    while (T--) solve();
    
    return 0;
}

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