Submission #534226

#TimeUsernameProblemLanguageResultExecution timeMemory
534226Haruto810198Collecting Stamps 3 (JOI20_ho_t3)C++17
100 / 100
125 ms133924 KiB
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = INT_MAX;
const int LNF = INF*INF;
const int MOD = 1000000007;
const double eps = 1e-12;

// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")

const int MAX = 210;

int n, L;
int pos[MAX];
int lim[MAX];
int dp[MAX][MAX][MAX][2];

// dp[l][r][c][p] : min. time of visited l from left, r from right, collected c, now at l/r

signed main(){
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin>>n>>L;
	FOR(i, 1, n, 1){
		cin>>pos[i];
	}
	pos[n+1] = L;

	FOR(i, 1, n, 1){
		cin>>lim[i];
	}
	
	FOR(l, 0, n, 1){
		FOR(r, 0, n, 1){
			FOR(c, 0, n, 1){
				FOR(p, 0, 1, 1){
					dp[l][r][c][p] = LNF;
				}
			}
		}
	}
	dp[0][0][0][0] = dp[0][0][0][1] = 0;
	
	FOR(l, 0, n, 1){
		FOR(r, 0, n, 1){
			
			if(l + r >= n) break;

			FOR(c, 0, n, 1){
				// dp[l][r][c][0] -> dp[l+1][r][?][0], dp[l][r+1][?][1]
				int tol = dp[l][r][c][0] + (pos[l+1] - pos[l]);
				int tor = dp[l][r][c][0] + (pos[l] + L - pos[n-r]);
				int cl = c + (tol <= lim[l+1]);
				int cr = c + (tor <= lim[n-r]);
				dp[l+1][r][cl][0] = min(dp[l+1][r][cl][0], tol);
				dp[l][r+1][cr][1] = min(dp[l][r+1][cr][1], tor);

				// dp[l][r][c][1] -> dp[l+1][r][?][0], dp[l][r+1][?][1]
				tol = dp[l][r][c][1] + (L - pos[n-r+1] + pos[l+1]);
				tor = dp[l][r][c][1] + (pos[n-r+1] - pos[n-r]);
				cl = c + (tol <= lim[l+1]);
				cr = c + (tor <= lim[n-r]);
				dp[l+1][r][cl][0] = min(dp[l+1][r][cl][0], tol);
				dp[l][r+1][cr][1] = min(dp[l][r+1][cr][1], tor);
			}
		}
	}
	
	int res = 0;
	FOR(l, 0, n, 1){
		FOR(r, 0, n, 1){
			FOR(c, 0, n, 1){
				FOR(p, 0, 1, 1){
					if(dp[l][r][c][p] < LNF) res = max(res, c);
				}
			}
		}
	}

	cout<<res<<'\n';

	return 0;

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...