oj.uz

Submission #976036

# Submission time Handle Problem Language Result Execution time Memory
976036 2024-05-06T05:42:34 Z vjudge1 Watching (JOI13_watching) C++17
100 / 100
 385 ms 31916 KB 
#include <bits/stdc++.h>
#define int long long
#define f first
#define s second
#define pb push_back
#define endl '\n'
using namespace std;

int N,K,B,a[2005];
int bob[2005][2005];

bool check(int x) {
	int kk = min(K, N + 1);
	int bb = min(B, N + 1);
	for (int i = 0; i <= kk; i++) {
		for (int j = 0; j <= bb; j++) {
			bob[i][j] = -1;
		}
	} 
	queue<pair<int, pair<int, int>>> p;
	p.push({1, {kk, bb}});
	bob[kk][bb] = 1;
	while (!p.empty()) {
		auto cur = p.front();
		p.pop();
		int idx = cur.f;
		int ku = cur.s.f;
		int bu = cur.s.s;
		if (bob[ku][bu] > idx) continue;
		// cout << idx << ' ' << ku << ' ' << bu << endl;
		if (idx >= N + 1) return true;
		int nxt_idx = idx;
		if (ku > 0) {
			while (a[nxt_idx + 1] - a[idx] + 1 <= x && nxt_idx <= N) nxt_idx++;
			if (bob[ku - 1][bu] < nxt_idx) {
				p.push({nxt_idx + 1, {ku - 1, bu}});
				bob[ku - 1][bu] = nxt_idx;
			}
		}
		if (bu > 0) {
			while (a[nxt_idx + 1] - a[idx] + 1 <= 2 * x && nxt_idx <= N) nxt_idx++;
			if (bob[ku][bu - 1] < nxt_idx) {
				bob[ku][bu - 1] = nxt_idx;
				p.push({nxt_idx + 1, {ku, bu - 1}});
			}
		}
	}
	return false;
}

void solve() {
	cin >> N >> K >> B;
	for (int i = 1; i <= N; i++) cin >> a[i];
	sort(a + 1, a + 1 + N);
	int l = 1;
	int r = 1e9;
	int ans = -1;
	while (l <= r) {
		int mid = (l + r) / 2;
		if (check(mid)) {
			ans = mid;
			r = mid - 1;
		}
		else l = mid + 1;
	} cout << ans << endl;
}

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int tttt = 1;
	// cin >> tttt;
	while (tttt--) solve();
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 2 ms 2396 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 267 ms 25292 KB Output is correct
4 Correct 46 ms 31324 KB Output is correct
5 Correct 26 ms 2900 KB Output is correct
6 Correct 385 ms 31916 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 23 ms 2652 KB Output is correct
9 Correct 41 ms 12856 KB Output is correct
10 Correct 63 ms 31340 KB Output is correct
11 Correct 31 ms 2848 KB Output is correct
12 Correct 176 ms 17060 KB Output is correct
13 Correct 2 ms 2396 KB Output is correct
14 Correct 1 ms 2392 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct