Submission #1045007

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045007		TAhmed33	Collecting Stamps 3 (JOI20_ho_t3)	C++98	100 / 100	193 ms	131676 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 2e9;
int dp[203][203][203][2];
int n, l, a[203], t[203];
int ans (int x, int y, int z, int c) { //left, right, count, is it at right?
	if (x == n + 1 && y == 0) {
		if (z == 0) return 0;
		return inf;
	}
	if (z < 0) return inf;
	int &ret = dp[x][y][z][c];
	if (ret != -1) return ret;
	ret = inf;
	if (c == 0) {
		if (x != n + 1) {
			if (y != 0) {
				int cost = l - a[x] + a[y];
				ret = min(ret, ans(x + 1, y, z, 1) + cost);
				if (ans(x + 1, y, z - 1, 1) + cost <= t[x]) {
					ret = min(ret, ans(x + 1, y, z - 1, 1) + cost);
				}
			}
			if (x != n + 1) {
				int cost = a[x + 1] - a[x];
				ret = min(ret, ans(x + 1, y, z, 0) + cost);
				if (ans(x + 1, y, z - 1, 0) + cost <= t[x]) {
					ret = min(ret, ans(x + 1, y, z - 1, 0) + cost);
				}
			}
		}
	} else {
		if (y != 0) {
			if (x != n + 1) {
				int cost = l - a[x] + a[y];
				ret = min(ret, ans(x, y - 1, z, 0) + cost);
				if (ans(x, y - 1, z - 1, 0) + cost <= t[y]) {
					ret = min(ret, ans(x, y - 1, z - 1, 0) + cost);
				}
			}
			if (y != 0) {
				int cost = a[y] - a[y - 1];
				ret = min(ret, ans(x, y - 1, z, 1) + cost);
				if (ans(x, y - 1, z - 1, 1) + cost <= t[y]) {
					ret = min(ret, ans(x, y - 1, z - 1, 1) + cost);
				}
			}
		}
	}
	return ret;
}
void solve () {
	cin >> n >> l;
	a[0] = 0; a[n + 1] = l;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= n; i++) {
		cin >> t[i];
	}
	memset(dp, -1, sizeof(dp));
	int ret = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= n + 1; j++) {
			for (int k = j + 1; k <= n + 1; k++) {
				if (ans(k, j, i, 0) != inf || ans(k, j, i, 1) != inf) {
					ret = i;
				}
			}
		}
	}
	cout << ret << '\n';
}		
signed main () {
	ios::sync_with_stdio(0); cin.tie(0);
	int tc = 1; //cin >> tc;
	while (tc--) solve();
}

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