제출 #767468

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
767468		NK_	Collecting Stamps 3 (JOI20_ho_t3)	C++17	15 / 100	70 ms	91604 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 = 1e9+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

	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);
						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;
						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][i+1][k + get][1], nt);
					}
				}
			}
		}
	}

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

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