Submission #534226

#	Time	Username	Problem	Language	Result	Execution time	Memory
534226		Haruto810198	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	125 ms	133924 KiB

ho_t3

#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;

}

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