Submission #1165590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165590		Nomio	Collecting Stamps 3 (JOI20_ho_t3)	C++20	100 / 100	86 ms	132168 KiB

ho_t3

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

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