Submission #540419

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
540419	2022-03-20T10:15:27 Z	RaresFelix	Watching (JOI13_watching)	C++17	100 / 100	211 ms	32764 KB

watching

#include <bits/stdc++.h>
#define MN 2071

using namespace std;

using ll = long long;

ll n, p, q, A[MN], DP[MN][MN];

bool ok(int len) {
	if(p + q >= n) return 1;
	///DP[poz][nr_mici]
	int lsmall = 1, lbig = 1;
	DP[1][0] = 1;
	DP[1][1] = 0;
	for(int i = 1; i <= n; ++i) {
		while(A[i] - A[lsmall] >= len) ++lsmall;
		while(A[i] - A[lbig] >= 2 * len) ++lbig;
		for(int j = 0; j <= min(p, n); ++j)
			DP[i][j] = min((!!j) * DP[lsmall-1][j-1] + (!j) * INT_MAX, DP[lbig-1][j] + 1);
	}
	return DP[n][p] <= q;
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
	cin >> n >> p >> q;
	for(int i = 1; i <= n; ++i) cin >> A[i];
	sort(A + 1, A + n + 1);
	ll st = 1, dr = 1e9, mij;
	while(st < dr) {
		mij = (st + dr) >> 1;
		if(ok(mij)) dr = mij;
		else st = mij + 1;
	}
	cout << st << "\n";
    return 0;
}

Subtask #1

50.0 / 50.0

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

Subtask #2

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	8404 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	356 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	6 ms	8532 KB	Output is correct
8	Correct	20 ms	10368 KB	Output is correct
9	Correct	99 ms	20152 KB	Output is correct
10	Correct	211 ms	32764 KB	Output is correct
11	Correct	15 ms	9808 KB	Output is correct
12	Correct	116 ms	23720 KB	Output is correct
13	Correct	7 ms	8576 KB	Output is correct
14	Correct	7 ms	8660 KB	Output is correct
15	Correct	8 ms	8656 KB	Output is correct