Submission #410728

#	Time	Username	Problem	Language	Result	Execution time	Memory
410728		ngpin04	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	204 ms	130760 KiB

ho_t3

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define int long long 
using namespace std;
const int N = 205;
const long long oo = 1e18;

long long dp[N][N][N][2];

int costl[N];
int costr[N];
int a[N];
int t[N];
int n,L;

template <typename T> 
bool mini(T &a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}

signed main() {	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> L;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= n; i++)
		cin >> t[i];

	a[++n] = L;	
	for (int i = 0; i < n; i++)
		costr[i] = a[i + 1] - a[i];

	for (int i = 1; i <= n; i++)
		costl[i % n] = a[i] - a[i - 1];

	// for (int i = 0; i < n; i++)
	// 	cerr << costr[i] << " \n"[i == n - 1];

	// for (int i = 0; i < n; i++)
	// 	cerr << costl[i] << " \n"[i == n - 1];

	for (int l = 0; l < n; l++) 
	for (int r = 0; r < n; r++)
	for (int cnt = 0; cnt < n; cnt++)
	for (int side = 0; side < 2; side++) 
		dp[l][r][cnt][side] = oo;
	
	dp[0][0][0][0] = dp[0][0][0][1] = 0;
	for (int l = 0, cntl = n; cntl > 0; l = (l + n - 1) % n, cntl--) 
	for (int r = 0, cntr = cntl - 1; cntr > 0; r = (r + 1) % n, cntr--) 
	for (int cnt = 0; cnt < n; cnt++) 
	for (int side = 0; side < 2; side++) {
		long long cur = dp[l][r][cnt][side];
		if (cur == oo)
			continue;

		int add = a[r] + (L - a[l]) % L;
		long long cost;

		cost = 1LL * (side == 0) * add + costr[r];
		int nxtr = (r + 1) % n;	
		mini(dp[l][nxtr][cnt + (cur + cost <= t[nxtr])][1], cur + cost);

		cost = 1LL * (side == 1) * add + costl[l];
		int nxtl = (l + n - 1) % n;
		mini(dp[nxtl][r][cnt + (cur + cost <= t[nxtl])][0], cur + cost);
	}

	int ans = 0;
	for (int cnt = 0; cnt < n; cnt++)
	for (int l = 0; l < n; l++)
	for (int r = 0; r < n; r++) 
	for (int side = 0; side < 2; side++)
		if (dp[l][r][cnt][side] < oo)
			ans = cnt;

	cout << ans;
	return 0;
}

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