Submission #464326

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
464326	2021-08-13T00:39:11 Z	Hamed5001	Watching (JOI13_watching)	C++14	100 / 100	322 ms	16156 KB

watching

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int mxN = 2e3+10, OO = 0x3f3f3f3f;
ll A[mxN], N, P, Q;
int dp[mxN][mxN];

bool ok(ll mid) {
	memset(dp, OO, sizeof dp);
	dp[0][0] = 0;

	for (int i = 0; i < N; i++) {
		int nxt_p = lower_bound(A, A+N, A[i] + mid) - A;
		int nxt_q = lower_bound(A, A+N, A[i] + 2 * mid) - A;
		for (int np = 0; np <= P; np++) {
			dp[nxt_p][np+1] = min(dp[nxt_p][np+1], dp[i][np]);
			dp[nxt_q][np] = min(dp[nxt_q][np], dp[i][np]+1);
		}
	}

	for (int i = 0; i <= P; i++) if (dp[N][i] <= Q) return 1;
	return 0;
}

void solve() {
	cin >> N >> P >> Q;
	P = min(P, N);
	Q = min(Q, N);
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}

	sort(A, A+N);

	ll l = 1, r = 1e10, mid;
	while(l < r) {
		mid = (l+r) >> 1;
		if (ok(mid)) r = mid;
		else l = mid+1;
	}
	cout << r << endl;
}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	solve();
}

Subtask #1

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	71 ms	16076 KB	Output is correct
2	Correct	68 ms	16076 KB	Output is correct
3	Correct	67 ms	16128 KB	Output is correct
4	Correct	70 ms	16108 KB	Output is correct
5	Correct	71 ms	16104 KB	Output is correct
6	Correct	69 ms	16112 KB	Output is correct
7	Correct	67 ms	16076 KB	Output is correct
8	Correct	72 ms	16120 KB	Output is correct
9	Correct	67 ms	16060 KB	Output is correct
10	Correct	65 ms	16116 KB	Output is correct
11	Correct	71 ms	16124 KB	Output is correct
12	Correct	70 ms	16108 KB	Output is correct
13	Correct	68 ms	16076 KB	Output is correct
14	Correct	66 ms	16112 KB	Output is correct
15	Correct	68 ms	16060 KB	Output is correct

Subtask #2

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	72 ms	16076 KB	Output is correct
2	Correct	69 ms	16128 KB	Output is correct
3	Correct	267 ms	16144 KB	Output is correct
4	Correct	321 ms	16076 KB	Output is correct
5	Correct	93 ms	16076 KB	Output is correct
6	Correct	322 ms	16148 KB	Output is correct
7	Correct	78 ms	16072 KB	Output is correct
8	Correct	92 ms	16140 KB	Output is correct
9	Correct	161 ms	16148 KB	Output is correct
10	Correct	301 ms	16144 KB	Output is correct
11	Correct	85 ms	16076 KB	Output is correct
12	Correct	194 ms	16092 KB	Output is correct
13	Correct	79 ms	16156 KB	Output is correct
14	Correct	84 ms	16076 KB	Output is correct
15	Correct	80 ms	16076 KB	Output is correct