제출 #1165590

#제출 시각아이디문제언어결과실행 시간메모리
1165590NomioCollecting Stamps 3 (JOI20_ho_t3)C++20
100 / 100
86 ms132168 KiB
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

ll dp[205][205][205][2];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	ll l;
	cin >> n >> l;
	ll x[n + 2], t[n + 1];
	for(int i = 1; i <= n; i++) {
		cin >> x[i];
	}
	x[0] = 0;
	x[n + 1] = l;
	for(int i = 1; i <= n; i++) {
		cin >> t[i];
	}
	for(int i = 0; i <= n + 1; i++) {
		for(int j = 0; j <= n + 1; j++) {
			for(int k = 0; k <= n; k++) {
				for(int p = 0; p < 2; p++) {
					dp[i][j][k][p] = 1e18;
				}
			}
		}
	}
	dp[0][n + 1][0][0] = dp[0][n + 1][0][1] = 0;
	for(int i = 0; i < n; i++) {
		for(int j = n + 1; j > i + 1; j--) {
			for(int k = 0; k <= n; k++) {
				ll X = min(dp[i][j][k][0] + x[i + 1] - x[i], dp[i][j][k][1] + l - (x[j] - x[i + 1]));
				if(X <= t[i + 1]) dp[i + 1][j][k + 1][0] = min(dp[i + 1][j][k + 1][0], X);
				else dp[i + 1][j][k][0] = min(dp[i + 1][j][k][0], X);
				X = min(dp[i][j][k][0] + l - (x[j - 1] - x[i]), dp[i][j][k][1] + x[j] - x[j - 1]);
				if(X <= t[j - 1]) dp[i][j - 1][k + 1][1] = min(dp[i][j - 1][k + 1][1], X);
				else dp[i][j - 1][k][1] = min(dp[i][j - 1][k][1], X); 
			}
		}
	}
	int ans = 0;
	for(int i = 0; i <= n + 1; i++) {
		for(int j = 0; j <= n + 1; j++) {
			for(int k = 0; k <= n; k++) {
				for(int p = 0; p < 2; p++) {
					if(dp[i][j][k][p] != 1e18) {
						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...