oj.uz

Submission #1101640

# Submission time Handle Problem Language Result Execution time Memory
1101640 2024-10-16T13:07:52 Z stdfloat Watching (JOI13_watching) C++17
100 / 100
 484 ms 21608 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define ff	first
#define ss	second
#define pii	pair<int, int>

#define sz(v)	(int)(v).size()
#define all(v)	(v).begin(), (v).end()

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

	int n, p, q;
	cin >> n >> p >> q;

	p = min(n, p); q = min(n, q);

	vector<int> a(n + 1, INT_MIN);
	for (int i = 1; i <= n; i++)
		cin >> a[i];

	sort(1 + all(a));

	auto chk = [&](int md) -> bool {
		int x = 0, y = 0;
		vector<vector<pii>> dp(n + 1); dp[0] = {{0, 0}};
		for (int i = 1; i <= n; i++) {
			while (x < n && a[x + 1] <= a[i] - md) x++;
			while (y < n && a[y + 1] <= a[i] - (md << 1)) y++;

			vector<pii> v;
			for (auto j : dp[x])
				if (j.ff < p) v.push_back({j.ff + 1, j.ss});
			for (auto j : dp[y])
				if (j.ss < q) v.push_back({j.ff, j.ss + 1});

			sort(v.begin(), v.end());
			for (int j = 0; j < sz(v); j++)
				if (!j || dp[i].back().ss > v[j].ss) dp[i].push_back(v[j]);
		
			assert(sz(dp[i]) < n + 2);
		}

		return !dp[n].empty();
	};

	int l = 1, r = 1;
	while (!chk(r)) {
		l = r; r <<= 1;
	}

	while (l <= r) {
		int md = (l + r) >> 1;

		if (!chk(md)) l = md + 1;
		else r = md - 1;
	}

	cout << l;
}

Subtask #1
50.0 / 50.0

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

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 297 ms 21528 KB Output is correct
4 Correct 15 ms 2384 KB Output is correct
5 Correct 15 ms 2384 KB Output is correct
6 Correct 345 ms 21608 KB Output is correct
7 Correct 17 ms 592 KB Output is correct
8 Correct 233 ms 2372 KB Output is correct
9 Correct 232 ms 2444 KB Output is correct
10 Correct 31 ms 2384 KB Output is correct
11 Correct 35 ms 2468 KB Output is correct
12 Correct 484 ms 10836 KB Output is correct
13 Correct 11 ms 592 KB Output is correct
14 Correct 14 ms 716 KB Output is correct
15 Correct 14 ms 592 KB Output is correct