Submission #1143528

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143528		am_aadvik	Watching (JOI13_watching)	C++20	50 / 100	1095 ms	472 KiB

watching

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

bool comp(pair<int, int> a, int v) {return a.first < v;}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n, p, q; cin >> n >> p >> q;
	if ((p + q) >= n) { cout << 1; return 0; }
	vector<pair<int, int>> a(n);
	for (int i = 0; i < n; ++i) cin >> a[i].first;
	sort(a.begin(), a.end());
	for (int i = 0; i < n; ++i) a[i].second = i;

	int s = 0, e = 1e9, ans = -1;
	while (s <= e) {
		int w = (s + e) / 2;
		vector<int> cur(n + 1, 1e9), prv(n + 1, 1e9);
		for (int cp = 0; cp <= p; ++cp) {
			for (int i = n - 1; i >= 0; --i) {
				if (cp > 0) {
					auto it = lower_bound(a.begin(), a.end(), a[i].first + w, comp);
					if (it == a.end()) cur[i] = min(cur[i], 0);
					else cur[i] = min(cur[i], prv[(*it).second]);
				}
				auto it = lower_bound(a.begin(), a.end(), a[i].first + w + w, comp);
				if (it == a.end()) cur[i] = min(cur[i], 1);
				else cur[i] = min(cur[i], 1 + cur[(*it).second]);
			}
			prv = cur, cur.assign(n + 1, 1e9);
		}
		if (prv[0] <= q) ans = w, e = w - 1;
		else s = w + 1;
	}
	cout << ans;
}

• Subtask 1: 50 / 50
• Subtask 2: 0 / 50