Submission #1325989

#	Time	Username	Problem	Language	Result	Execution time	Memory
1325989		tkm_algorithms	Collecting Stamps 3 (JOI20_ho_t3)	C++20	0 / 100	0 ms	332 KiB

ho_t3

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using P = pair<int, int>;
#define all(x) x.begin(), x.end()
#define rep(i, l, n) for (int i = l; i < (n); ++i)
#define sz(x) (int)x.size()
const char nl = '\n';
const int mod = 998244353;
const int inf = 1e9+10;

void mnu(int &a, int b) {
	if (b < a)a = b;
}

void solve() {
	int n, l; cin >> n >> l;
	vector<int> a(1, 0), t(n+1);
	rep(i, 0, n) {
		int x; cin >> x;
		a.push_back(x);
	}
	
	//vector<int> 
	rep(i, 1, n+1)cin >> t[i];
	
	vector<int> b(1, 0);
	for (int i = n; i >= 1; --i)b.push_back(a[i]);
	
	int dp[n+1][n+1][2][n+1];
	rep(i, 0, n+1)
		rep(j, 0, n+1)
			rep(w, 0, 2)
				rep(cnt, 0, n+1)
					dp[i][j][w][cnt] = inf;
		
	rep(i, 1, n+1) {
		if (l-b[i] <= t[n-i+1])dp[0][i][0][1] = dp[0][i][1][1] = l-b[i];
		if (a[i] <= t[i])dp[i][0][1][1] = dp[i][0][0][1] = a[i];
	}
	b[0] = l;
				
	rep(i, 0, n+1) {
		rep(j, 0, n+1) {
			if (n < i+j || i+j==0)continue;
			rep(cnt, 1, n+1) {
				if (i)
					mnu(dp[i][j][1][cnt], dp[i-1][j][1][cnt]+l-b[j]+a[i]);
					//mnu(dp[i][j][0][cnt], dp[i-1][j][0][cnt]+a[i]-a[i-1]);
				if (j)
					//mnu(dp[i][j][1][cnt], dp[i][j-1][1][cnt]+b[j-1]-b[j]);
					mnu(dp[i][j][0][cnt], dp[i][j-1][0][cnt]+a[i]+l-b[j]);
					
				//if (j)
					//mnu(dp[i][j][0][cnt], dp[i][j-1][0][cnt]);
				if (i) {
					if (dp[i-1][j][0][cnt-1]+a[i]-a[i-1] <= t[i])mnu(dp[i][j][0][cnt], dp[i-1][j][0][cnt-1]+a[i]-a[i-1]);
					if (dp[i-1][j][1][cnt-1]+l-b[j]+a[i] <= t[i])mnu(dp[i][j][0][cnt], dp[i-1][j][1][cnt-1]+l-b[j]+a[i]);
				}
				if (j) {
					if (dp[i][j-1][0][cnt-1]+a[i]+l-b[j] <= t[n-j+1])mnu(dp[i][j][1][cnt], dp[i][j-1][0][cnt-1]+a[i]+l-b[j]);
					if (dp[i][j-1][1][cnt-1]+b[j-1]-b[j] <= t[n-j+1])mnu(dp[i][j][1][cnt], dp[i][j-1][1][cnt-1]+b[j-1]-b[j]);
				}
			}
		}
			
	}
	
	int res = 0;
	rep(i, 0, n+1)
		rep(j, 0, n+1)
			rep(cnt, 1, n+1) {
				if (dp[i][j][0][cnt] != inf) {
					res = max(res, cnt);
				}
				if (dp[i][j][1][cnt] != inf) {
					res = max(res, cnt);
				}
			}
			
	cout << res << nl;
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

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