Submission #767524

#	Time	Username	Problem	Language	Result	Execution time	Memory
767524		NK_	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	457 ms	448848 KiB

ho_t3

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define sz(x) signed(x.size())
#define int long long

template<class T> using V = vector<T>;

const int INF = 1e15+10;


signed main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, L; cin >> N >> L;
	V<int> A(N), T(N);

	for(auto& x : A) cin >> x;
	for(auto& x : T) cin >> x;

	A.insert(begin(A), 0); T.insert(begin(T), -1);
	A.push_back(0); T.push_back(-1);

	// for(auto& x : A) cout << x << " ";
	// cout << endl;
	// for(auto& x : T) cout << x << " ";
	// cout << endl;

	// dp[SFX][PFX][K][2] = min time

	V<V<V<V<int>>>> dp(N + 1, V<V<V<int>>>(N + 1, V<V<int>>(N + 1, V<int>(2, INF))));
	// int dp[N + 1][N + 1][N + 1][2];
	// for(int i = 0; i <= N; i++) for(int j = 0; j <= N; j++) {
	// 	for(int k = 0; k <= N; k++) for(int l = 0; l < 2; l++) {
	// 		dp[i][j][k][l] = INF;
	// 	}
	// }

	int ans = 0;
	dp[0][0][0][0] = 0;
	for(int w = 0; w <= N; w++) {
		for(int s = 0; s <= N; s++) {
			int p = w - s; if (p < 0) continue;

			for(int k = 0; k <= N; k++) for(int x = 0; x < 2; x++) if (dp[s][p][k][x] != INF) {
				// cout << s << " " << p << " " << k << " " << x << " -> " << dp[s][p][k][x] << endl;
				ans = max(ans, k);
				
				int i = (x == 0 ? sz(A) - 1 - s : p);
				if (w+1 <= N) {
					// move left
					{
						int ni = (sz(A) - 1 - s - 1); 
						// cout << ni << endl;
						int nt = dp[s][p][k][x] + min(L - abs(A[i] - A[ni]), abs(A[i] - A[ni]));
						// cout << "LEFT: " << nt << endl;
						int get = (T[ni] >= nt);
						dp[s+1][p][k + get][0] = min(dp[s+1][p][k + get][0], nt);
					}


					// move right
					{
						int ni = p + 1;
						// cout << ni << endl;
						int nt = dp[s][p][k][x] + min(L - abs(A[i] - A[ni]), abs(A[i] - A[ni]));
						// cout << "RIGHT: " << nt << endl;
						int get = (T[ni] >= nt);
						dp[s][p+1][k + get][1] = min(dp[s][p+1][k + get][1], nt);
					}
				}
			}
		}
	}

	cout << ans << nl;
    return 0;
}

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