Submission #264582

#	Time	Username	Problem	Language	Result	Execution time	Memory
264582		ruler	Watching (JOI13_watching)	C++14	100 / 100	259 ms	16256 KiB

watching

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

#define endl '\n'
#define ends ' '
#define endt '\t'
#define die(x) return cout << x << endl, 0
#define all(v) v.begin(), v.end()
#define sz(x) (int)(x.size())
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << ends << H; debug_out(T...); }
#define debug(...) cerr << "{" << #__VA_ARGS__ << "}:", debug_out(__VA_ARGS__)
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9;
const ll MOD = 1e9 + 7;

////////////////////////////////////////////////////////////////////
 
const int N = 2e3 + 5;

int n, p, q, A[N], DP[N][N], P[N], Q[N];

bool IsVal(int w) {
	P[0] = Q[0] = 0;
	for (int i = 0; i < n; i++) {
		if (i) P[i] = P[i - 1];
		while (P[i] < n && A[i] + w - 1 >= A[P[i]]) P[i]++;
	}
	for (int i = 0; i < n; i++) {
		if (i) Q[i] = Q[i - 1];
		while (Q[i] < n && A[i] + w + w - 1 >= A[Q[i]]) Q[i]++;
	}
	P[n] = Q[n] = n;
	memset(DP, 0, sizeof DP);
	for (int i = 0; i <= p; i++) for (int j = 0; j <= q; j++) {
		if (i < p) DP[i + 1][j] = max(DP[i + 1][j], P[DP[i][j]]);
		if (j < q) DP[i][j + 1] = max(DP[i][j + 1], Q[DP[i][j]]);
	}
	return DP[p][q] == n;
}

int main() {
 
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	mt19937 Rnd(time(0));

	cin >> n >> p >> q;
	for (int i = 0; i < n; i++) cin >> A[i];
	sort(A, A + n);
	if (p + q >= n) die(1);
	int dw = 0, up = INF + 1;
	while (up - dw > 1) {
		int md = (dw + up) >> 1;
		if (IsVal(md)) up = md;
		else dw = md;
	}
	cout << up << endl;

	return 0;
}

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