Submission #764686

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
764686	2023-06-23T21:07:05 Z	NK_	Watching (JOI13_watching)	C++17	100 / 100	357 ms	16116 KB

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 / (P + Q);
	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.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct

Subtask #2

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	340 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	261 ms	12244 KB	Output is correct
4	Correct	357 ms	16116 KB	Output is correct
5	Correct	16 ms	996 KB	Output is correct
6	Correct	355 ms	16096 KB	Output is correct
7	Correct	4 ms	468 KB	Output is correct
8	Correct	24 ms	1428 KB	Output is correct
9	Correct	128 ms	6316 KB	Output is correct
10	Correct	334 ms	15316 KB	Output is correct
11	Correct	16 ms	1092 KB	Output is correct
12	Correct	186 ms	8092 KB	Output is correct
13	Correct	4 ms	496 KB	Output is correct
14	Correct	5 ms	468 KB	Output is correct
15	Correct	6 ms	468 KB	Output is correct