Submission #1301945

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301945		pasta	Watching (JOI13_watching)	C++20	100 / 100	184 ms	38256 KiB

watching

//Oh? You're Approaching Me?

#include <bits/stdc++.h>
using namespace std;

#define int long long
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;


//#pragma GCC optimize("O3,unroll-loops")
#define migmig     		ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb          		push_back
#define F           		first
#define S           		second
#define SZ(x)       		ll((x).size())
#define all(x)      		(x).begin(), (x).end()
#define cl          		clear
#define endl        		'\n'
#define deb(x)    			cerr << #x << " = " << x << '\n'
#define dokme(x)			{cout << x << endl; return;}
#define wtf					cout << "[ahaaaaaaaaaaaaaaaa]" << endl;

const int maxn = 3000 + 10;
const int mod = 1e9 + 7; //998244353
const int inf = 1e9 + 5;
const int LOG = 24;

//g++ main.cpp -o main && main.exe

int n, p, q, a[maxn], l1[maxn], l2[maxn], dp[maxn][maxn];


bool check(int x) {
	for (int i = 1; i <= n; i++) {
		l1[i] = upper_bound(a + 1, a + n + 1, a[i] - x) - a;
		l2[i] = upper_bound(a + 1, a + n + 1, a[i] - 2 * x) - a;
		// deb(i);
		// cout << l1[i] << ' ' << l2[i] << '\n';
	}
	dp[0][0] = 0;
	for (int i = 1; i <= n; i++) {
		dp[i][0] = dp[l2[i] - 1][0] + 1;
		for (int j = 1; j <= p; j++) {
			dp[i][j] = dp[i][j - 1];
			dp[i][j] = min(dp[i][j], dp[l1[i] - 1][j - 1]);
			dp[i][j] = min(dp[i][j], dp[l2[i] - 1][j] + 1);
		}
	}
	// deb(dp[2][1]);
	return (dp[n][p] <= q);
}

signed main() {
	cin >> n >> p >> q;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	sort(a + 1, a + n + 1);
	if (p >= n || q >= n) {
		cout << 1 << '\n';
		return 0;
	}

	 int l = 0, r = 2 * inf;
	 while (r - l > 1) {
	 	int mid = (l + r) / 2;
	 	if (check(mid))
	 		r = mid;
	 	else
	 		l = mid;
	 }
	 cout << r << '\n';
//	cout << check(3) << '\n';
//	deb(dp[3][1]);
//	deb(l2[3]);
}

// 3 1 1
// 2
// 11
// 17

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