Submission #861666

#	Time	Username	Problem	Language	Result	Execution time	Memory
861666		dsyz	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	119 ms	129064 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N,L;
	cin>>N>>L;
	ll X[N + 2], T[N + 2];
	for(ll i = 1;i <= N;i++){
		cin>>X[i];
	}
	for(ll i = 1;i <= N;i++){
		cin>>T[i];
	}
	X[0] = 0, T[0] = -1;
	X[N + 1] = L, T[N + 1] = -1;
	ll dp[N + 2][N + 2][N + 1][2];
	for(ll l = 0;l <= N + 1;l++){
		for(ll r = 0;r <= N + 1;r++){
			for(ll k = 0;k <= N;k++){
				dp[l][r][k][0] = 1e18;
				dp[l][r][k][1] = 1e18;
			}
		}
	}
	dp[0][N + 1][0][0] = 0;
	dp[0][N + 1][0][1] = 0;
	for(ll l = 0;l <= N + 1;l++){
		for(ll r = N + 1;r > l;r--){
			for(ll k = 0;k <= N;k++){
				if(l >= 1){
					dp[l][r][k][0] = min(dp[l][r][k][0],dp[l - 1][r][k - 1][0] + min(X[l] - X[l - 1],L - (X[l] - X[l - 1])));
					dp[l][r][k][0] = min(dp[l][r][k][0],dp[l - 1][r][k - 1][1] + min(X[r] - X[l],L - (X[r] - X[l])));
					if(dp[l][r][k][0] > T[l]) dp[l][r][k][0] = 1e18;
					
					dp[l][r][k][0] = min(dp[l][r][k][0],dp[l - 1][r][k][0] + min(X[l] - X[l - 1],L - (X[l] - X[l - 1])));
					dp[l][r][k][0] = min(dp[l][r][k][0],dp[l - 1][r][k][1] + min(X[r] - X[l],L - (X[r] - X[l])));
				}
				if(r <= N){
					dp[l][r][k][1] = min(dp[l][r][k][1], dp[l][r + 1][k - 1][1] + min(X[r + 1] - X[r],L - (X[r + 1] - X[r])));
                    dp[l][r][k][1] = min(dp[l][r][k][1], dp[l][r + 1][k - 1][0] + min(X[r] - X[l],L - (X[r] - X[l])));
                    if(dp[l][r][k][1] > T[r]) dp[l][r][k][1] = 1e18;
                    
                    dp[l][r][k][1] = min(dp[l][r][k][1], dp[l][r + 1][k][1] + min(X[r + 1] - X[r],L - (X[r + 1] - X[r])));
                    dp[l][r][k][1] = min(dp[l][r][k][1], dp[l][r + 1][k][0] + min(X[r] - X[l],L - (X[r] - X[l])));
				}
			}
		}
	}
	ll ans = 0;
	for(ll l = 0;l <= N + 1;l++){
		for(ll r = 0;r <= N + 1;r++){
			for(ll k = 0;k <= N;k++){
				if(min(dp[l][r][k][0],dp[l][r][k][1]) < 1e18){
					ans = max(ans,k);
				}
			}
		}
	}
	cout<<ans<<'\n';
}

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