oj.uz

Submission #856385

# Submission time Handle Problem Language Result Execution time Memory
856385 2023-10-03T09:38:50 Z qthang2k11 Collecting Stamps 3 (JOI20_ho_t3) C++17
0 / 100
 59 ms 512596 KB 
// dinhmanhhungwillwinioi2024
#include <bits/stdc++.h>
using namespace std;

const int N = 403, MAX = 1e9;

int n, limit, t[N], dp[N][N][N][2];

struct Data {
	int pos, t;
	Data(int pos = 0, int t = 0):
		pos(pos), t(t) {}
} a[N];

int32_t main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> limit;
	for (int i = 1; i <= n; i++)
		cin >> a[i].pos;
	for (int i = 1; i <= n; i++)
		cin >> a[i].t;
	if (n == 1) {
		if (a[1].pos <= a[1].t || limit - a[1].pos <= a[1].t)
			cout << 1;
		else cout << 0;
		return 0;
	}
	for (int i = 1; i <= n; i++)
		a[i + n] = a[i], a[i + n].pos += limit;
	memset(dp, 63, sizeof dp);
	bool tmp = (limit - a[n].pos) <= a[n].t;
	dp[n][n][tmp][0] = dp[n][n][tmp][1] = limit - a[n].pos;
	tmp = (a[n + 1].pos <= a[n + 1].t);
	dp[n + 1][n + 1][tmp][0] = dp[n + 1][n + 1][tmp][1] = a[n + 1].pos;
	int m = (n << 1), ans = 0;
	for (int l = n + 1; l > 0; l--) {
		for (int r = l; r <= m; r++) {
			for (int k = r - l + 1; k >= 0; k--) {
				for (int s = 0; s < 2; s++) {
					int cur = dp[l][r][k][s];
					if (cur > MAX || r - n >= l) continue;
					ans = max(ans, k);
					if (r + 1 <= m && (l > n || r + 1 - n < l)) {
						int cost = a[r + 1].pos - (s ? a[r].pos : a[l].pos);
						if (cost <= MAX && cur + cost < dp[l][r + 1][k + (cur + cost <= a[r + 1].t)][1])
							dp[l][r + 1][k + (cur + cost <= a[r + 1].t)][1] = cur + cost;
					}
					if (l - 1 > 0 && (r <= n || l - 1 > r - n)) {
						int cost = (s ? a[r].pos : a[l].pos) - a[l - 1].pos;
						if (cost <= MAX && cur + cost < dp[l - 1][r][k + (cur + cost <= a[l - 1].t)][0])
							dp[l - 1][r][k + (cur + cost <= a[l - 1].t)][0] = cur + cost;
					}
				}
			}
		}
	}
	cout << ans;
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 512552 KB Output is correct
2 Incorrect 55 ms 512596 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 512552 KB Output is correct
2 Incorrect 55 ms 512596 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 512552 KB Output is correct
2 Incorrect 55 ms 512596 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 512552 KB Output is correct
2 Incorrect 55 ms 512596 KB Output isn't correct
3 Halted 0 ms 0 KB -