제출 #1286406

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286406		third	Collecting Stamps 3 (JOI20_ho_t3)	C++20	100 / 100	136 ms	132216 KiB

ho_t3

#include<bits/stdc++.h>
typedef long long ll;
#define pii pair<ll, ll>
#define fi first
#define se second
#define endl '\n'
#define TASK ""
#define N 200005
#define LOG 17
using namespace std;

bool ghuy4g;

const ll inf = 1e16;

ll n, L;
pii a[N];

ll dis(ll i, ll j) {
	if (i > j) swap(i, j);
	if (j == n + 1) {
		return min(a[i].fi, L - a[i].fi);
	}
	return min(a[j].fi - a[i].fi, L - a[j].fi + a[i].fi);
}

ll dp[205][205][205][2];

void solve() {
	a[n + 1].fi = 0;
	for (int i = 0; i <= n + 1; i ++) {
		for (int j = 0; j <= n + 1; j ++) {
			for (int z = 0; z <= n + 1; z ++) {
				for (int t = 0; t < 2; t ++) {
					dp[i][j][z][t] = inf;
				}
			}
		}
	}
	ll ans = 0;
	dp[0][0][0][0] = dp[0][0][0][1] = 0;
	dp[0][n + 1][0][0] = dp[0][n + 1][0][1] = 0;
	for (int i = 0; i <= n; i ++) {
		for (int j = n + 1; j >= 1; j --) {
			if (j <= i) continue;
			for (int cnt = 0; cnt <= n; cnt ++) {
				if (i > 0) dp[i][j][cnt][0] = min(dp[i][j][cnt][0], dp[i - 1][j][cnt][0] + dis(i, i - 1));
				if (i > 0) dp[i][j][cnt][0] = min(dp[i][j][cnt][0], dp[i - 1][j][cnt][1] + dis(i, j));
				if (j <= n) dp[i][j][cnt][1] = min(dp[i][j][cnt][1], dp[i][j + 1][cnt][0] + dis(i, j));
				if (j <= n) dp[i][j][cnt][1] = min(dp[i][j][cnt][1], dp[i][j + 1][cnt][1] + dis(j + 1, j));
				if (i > 0 && cnt > 0) {
					ll xet = dp[i - 1][j][cnt - 1][0] + dis(i - 1, i);
					xet = min(xet, dp[i - 1][j][cnt - 1][1] + dis(j, i));
					//dp[i][j][cnt][0] = min(dp[i][j][cnt][0], xet);
					if (xet <= a[i].se) {
						dp[i][j][cnt][0] = min(dp[i][j][cnt][0], xet);
					}
				}
				if (j <= n && cnt > 0) {
					ll xet = dp[i][j + 1][cnt - 1][1] + dis(j + 1, j);
					xet = min(xet, dp[i][j + 1][cnt - 1][0] + dis(i, j));
					if (xet <= a[j].se) {
						dp[i][j][cnt][1] = min(dp[i][j][cnt][1], xet);
					}
				}
				if (dp[i][j][cnt][0] <= a[i].se || dp[i][j][cnt][1] <= a[j].se) {
					ans = max(ans, (ll)cnt);
				}
			}
		}
	}
	cout << ans << endl;
}

bool klinh;

signed main() {
   // freopen("test.inp", "r", stdin);
	//freopen("test.out", "w", stdout);
	//srand(time(0));
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> L;
    for (int i = 1; i <= n; i ++) {
    	cin >> a[i].fi;
    }
    for (int i = 1; i <= n; i ++) {
    	cin >> a[i].se;
    }
    sort(a + 1, a + 1 + n);
    
    solve();
   	
   	cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
}

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