Submission #1251858

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251858		marda	Watching (JOI13_watching)	C++20	100 / 100	571 ms	31992 KiB

watching

#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <vector>
#include <tuple>

#define endl "\n"
#define int long long int
#define ld long double
#define mp make_pair
#define pb push_back
#define Bound 1e9 + 5

using namespace std;

int n, p, q;
vector<int> arr;

bool cam(int mid) {

	vector<vector<int>> dp(n + 5, vector<int>(n + 5, Bound));

	for (int i = 0; i <= n; i++) dp[0][i] = 0;

	for (int i = 1; i <= n; i++) {
		int id1 = lower_bound(arr.begin(), arr.end(), arr[i - 1] - mid + 1) - arr.begin();
		int id2 = lower_bound(arr.begin(), arr.end(), arr[i - 1] - 2 * mid + 1) - arr.begin();

		for (int j = 0; j <= n; j++) {
			if (j != 0) dp[i][j] = min(dp[i][j], dp[id1][j - 1]);

			dp[i][j] = min(dp[i][j], dp[id2][j] + 1);
		}
	}

	bool doit = false;
	for (int i = 0; i <= n; i++) {
		if (i <= p && dp[n][i] <= q) doit = true;
	}

	return doit;

}

int32_t main()
{

	cin >> n >> p >> q;

	for (int i = 1; i <= n; i++) {
		int a;
		cin >> a;
		arr.pb(a);
	}
	sort(arr.begin(), arr.end());

	int l = 1, r = Bound, w = 1;

	while (l <= r) {
		int mid = (l + r) / 2;

		if (cam(mid)) r = mid - 1, w = mid;
		else l = mid + 1;
	}
	cout << w << endl;

	return 0;
}

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