oj.uz

Submission #1101630

# Submission time Handle Problem Language Result Execution time Memory
1101630 2024-10-16T12:02:05 Z stdfloat Watching (JOI13_watching) C++17
100 / 100
 551 ms 21672 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)) 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 504 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 340 KB Output is correct
7 Correct 2 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 2 ms 336 KB Output is correct
10 Correct 3 ms 336 KB Output is correct
11 Correct 4 ms 336 KB Output is correct
12 Correct 3 ms 336 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 345 ms 21460 KB Output is correct
4 Correct 18 ms 2388 KB Output is correct
5 Correct 18 ms 2388 KB Output is correct
6 Correct 407 ms 21672 KB Output is correct
7 Correct 19 ms 596 KB Output is correct
8 Correct 299 ms 2448 KB Output is correct
9 Correct 263 ms 2456 KB Output is correct
10 Correct 33 ms 2388 KB Output is correct
11 Correct 45 ms 2388 KB Output is correct
12 Correct 551 ms 11060 KB Output is correct
13 Correct 11 ms 596 KB Output is correct
14 Correct 27 ms 732 KB Output is correct
15 Correct 15 ms 596 KB Output is correct