Submission #1151006

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151006		pinbu	Collecting Stamps 3 (JOI20_ho_t3)	C++20	5 / 100	651 ms	67960 KiB

ho_t3

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

const int N = 205;

int n, l, x[N], ti[N], dp[N][N][2][N];
int DP1(int p, int s, int d, int t) {
	if (p + 1 == s) return 0;
	int &T = dp[p][s][d][t];
	if (T >= 0) return T;
	
	T = 0;
	if (!d) {
		int tt = 0;
		for (int i = p + 1; i < s; i++) {
			tt += 2 * ((t + 1) / 2) * x[p] + 2 * (t / 2) * (l - x[s]) + x[i] <= ti[i];
			T = max(T, tt + DP1(i, s, 1, t + 1)); 
		}
	} else {
		int tt = 0;
		for (int i = s - 1; i > p; i--) {
			tt += 2 * ((t + 1) / 2) * x[p] + 2 * (t / 2) * (l - x[s]) + l - x[i] <= ti[i];
			T = max(T, tt + DP1(p, i, 0, t + 1)); 
		}
	}
	return T;
}
int DP2(int p, int s, int d, int t) {
	if (p + 1 == s) return 0;
	int &T = dp[p][s][d][t];
	if (T >= 0) return T;
	
	T = 0;
	if (d) {
		int tt = 0;
		for (int i = s - 1; i > p; i--) {
			tt += 2 * (t / 2) * x[p] + 2 * ((t + 1) / 2) * (l - x[s]) + l - x[i] <= ti[i];
			T = max(T, tt + DP2(p, i, 0, t + 1)); 
		}
	} else {
		int tt = 0;
		for (int i = p + 1; i < s; i++) {
			tt += 2 * (t / 2) * x[p] + 2 * ((t + 1) / 2) * (l - x[s]) + x[i] <= ti[i];
			T = max(T, tt + DP2(i, s, 1, t + 1)); 
		}
	}
	return T;
}
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];
	
	if (n == 1) return void(cout << (min(x[1], l - x[1]) <= ti[1]));
	memset(dp, -1, sizeof dp);
	cout << max(DP1(0, n + 1, 0, 0), DP2(0, n + 1, 1, 0));
}

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: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 75