Submission #764687

#	Time	Username	Problem	Language	Result	Execution time	Memory
764687		NK_	Watching (JOI13_watching)	C++17	100 / 100	538 ms	16184 KiB

watching

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

template<class T> using V = vector<T>;

const int INF = 1e9+10;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, P, Q; cin >> N >> P >> Q;
	P = min(P, N + 1), Q = min(Q, N + 1);

	V<int> A(N); for(auto& x : A) cin >> x;
	sort(begin(A), end(A));

	auto check = [&](int w) {
		V<V<int>> dp(N + 1, V<int>(P + 1, INF));
		dp[0][0] = 0;
		int RW = 0, R2W = 0;
		for(int i = 0; i < N; i++) for(int p = 0; p <= P; p++) {
			// cout << i << " <-> " << p << endl;
			if (p + 1 <= P) {
				int x = A[i] + w - 1;
				while(RW < N && A[RW] <= x) RW++;
				// cout << i << " " << RW << endl;
				dp[RW][p+1] = min(dp[RW][p+1], dp[i][p] + 1);
			}

			{
				int x = A[i] + 2 * w - 1;
				while(R2W < N && A[R2W] <= x) R2W++;
				// cout << i << " " << R2W << endl;
				dp[R2W][p] = min(dp[R2W][p], dp[i][p] + 1);
			}
			// cout << endl;
		}

		bool ans = 0;
		for(int p = 0; p <= P; p++) {
			int q = dp[N][p] - p;
			if (q <= Q) ans = 1;
		}

		return ans;
	};

	int lo = 1, hi = INF;
	while(lo < hi) {
		int mid = (lo + hi) / 2;

		if (check(mid)) hi = mid;
		else lo = mid + 1;
	}

	cout << lo << nl;



    return 0;
}

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