Submission #532539

#	Time	Username	Problem	Language	Result	Execution time	Memory
532539		amunduzbaev	Collecting Stamps 3 (JOI20_ho_t3)	C++17	15 / 100	98 ms	67748 KiB

ho_t3

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

#define ar array

const int N = 205;
int dp[2][N][N][N];
int x[N], t[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, L; cin>>n>>L;
	for(int i=1;i<=n;i++) cin>>x[i];
	for(int i=1;i<=n;i++) cin>>t[i];
	x[n + 1] = L;
	
	memset(dp, 127, sizeof dp);
	int MX = dp[0][0][0][0];
	dp[0][0][n+1][0] = 
	dp[1][0][n+1][0] = 0;

	int res = 0;
	for(int c=0;c<=n;c++){
		for(int l=0;l<=n;l++){
			for(int r=n+1;r>l;r--){
				dp[0][l][r][c] = min(dp[0][l][r][c], dp[1][l][r][c] + L - x[r] + x[l]);
				dp[1][l][r][c] = min(dp[1][l][r][c], dp[0][l][r][c] + L - x[r] + x[l]);
				if(dp[0][l][r][c] < MX) res = max(res, c);
				if(dp[1][l][r][c] < MX) res = max(res, c);
				//~ if(l == 0 && r == 1){
					//~ cout<<l<<" "<<r<<" "<<c<<" "<<dp[0][l][r][c]<<" "<<dp[1][l][r][c]<<"\n";
				//~ }


				dp[0][l+1][r][c] = min(dp[0][l+1][r][c], dp[0][l][r][c] + x[l+1] - x[l]);
				if(dp[0][l][r][c] + x[l+1] - x[l] <= t[l+1]){
					dp[0][l+1][r][c+1] = min(dp[0][l+1][r][c+1], dp[0][l][r][c] + x[l+1] - x[l]);
				}
				dp[1][l][r-1][c] = min(dp[1][l][r-1][c], dp[1][l][r][c] + x[r] - x[r-1]);
				if(dp[1][l][r][c] + x[r] - x[r-1] <= t[r-1]){
					dp[1][l][r-1][c+1] = min(dp[1][l][r-1][c+1], dp[1][l][r][c] + x[r] - x[r-1]);
				}
			}
		}
	}
	
	cout<<res<<"\n";
}

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