Submission #203345

#	Time	Username	Problem	Language	Result	Execution time	Memory
203345		staniewzki	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	83 ms	63864 KiB

ho_t3

#include<bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
const int N = 201;
int n, len, ans;
int dp[N][N][N][2];
int d[N], t[N];
int main() {
	cin >> n >> len;
	REP(i, n) cin >> d[i + 1];
	REP(i, n) cin >> t[i];
	REP(l, n + 1) REP(r, n + 1) REP(k, n + 1) REP(q, 2) dp[l][r][k][q] = 1e9 + 1;
	dp[0][0][0][0] = 0;
	dp[0][0][0][1] = 0;
	d[n + 1] = len;
	REP(l, n + 1) REP(r, n + 1) {
		if(n < l + r) break;
		REP(k, n + 1) {
			if(l) {
				dp[l][r][k][0] = min(dp[l][r][k][0], dp[l - 1][r][k][0] + d[l] - d[l - 1]);
				dp[l][r][k][0] = min(dp[l][r][k][0], dp[l - 1][r][k][1] + d[l] + len - d[n + 1 - r]);
			}
			if(r) {
				dp[l][r][k][1] = min(dp[l][r][k][1], dp[l][r - 1][k][1] + d[n + 2 - r] - d[n + 1 - r]);
				dp[l][r][k][1] = min(dp[l][r][k][1], dp[l][r - 1][k][0] + d[l] + len - d[n + 1 - r]);
			}
		}
		for(int k = n; k >= 1; k--) {
			if(l && dp[l][r][k - 1][0] <= t[l - 1]) {
				dp[l][r][k][0] = dp[l][r][k - 1][0];
				ans = max(ans, k);
			}
			if(r && dp[l][r][k - 1][1] <= t[n - r]) {
				dp[l][r][k][1] = dp[l][r][k - 1][1];
				ans = max(ans, k);
			}
		}
	}
	cout << ans << "\n";
}

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