답안 #540419

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
540419	2022-03-20T10:15:27 Z	RaresFelix	구경하기 (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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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