답안 #872133

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
872133	2023-11-12T11:07:05 Z	serifefedartar	구경하기 (JOI13_watching)	C++17	100 / 100	366 ms	16984 KB

watching

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9+9;
const ll LOGN = 20; 
const ll MAXN = 2005;

vector<int> A;
int dp[MAXN][MAXN], P, N, Q;
bool check(int w) {
	for (int i = 0; i < MAXN; i++) {
		for (int j = 0; j < MAXN; j++)
			dp[i][j] = 1e7;
	}

	dp[0][0] = 0;
	int r_w = 1, r_2w = 1;
	while (r_w != N && A[r_w + 1] - A[1] < w)
		r_w++;
	while (r_2w != N && A[r_2w + 1] - A[1] < 2*w)
		r_2w++;

	for (int i = 1; i <= N; i++) {
		for (int j = 0; j <= P; j++) {
			while (r_w != N && A[r_w + 1] - A[i] < w)
				r_w++;
			while (r_2w != N && A[r_2w + 1] - A[i] < 2*w)
				r_2w++;

			dp[r_w][j+1] = min(dp[r_w][j+1], dp[i-1][j]);
			dp[r_2w][j] = min(dp[r_2w][j], dp[i-1][j] + 1);
		}
	}

	for (int used_w = 0; used_w <= P; used_w++) {
		if (dp[N][used_w] <= Q)
			return true;
	}
	return false;
}

int main() {
	cin >> N >> P >> Q;

	if (P + Q >= N) {
		cout << "1\n";
		return 0;
	}

	A = vector<int>(N+1);
	A[0] = 0;
	for (int i = 1; i <= N; i++)
		cin >> A[i];
	sort(A.begin(), A.end());

	int L = 1;
	int R = 1e9;
	int ans = -1;
	while (R >= L) {
		int mid = L + (R-L)/2;
		if (check(mid)) {
			R = mid - 1;
			ans = mid;
		} else
			L = mid + 1;
	}
	cout << ans << "\n";
}

Subtask #1

50.0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	66 ms	16020 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	45 ms	15964 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	49 ms	16984 KB	Output is correct
8	Correct	61 ms	16152 KB	Output is correct
9	Correct	43 ms	16216 KB	Output is correct
10	Correct	42 ms	15960 KB	Output is correct
11	Correct	48 ms	16148 KB	Output is correct
12	Correct	55 ms	16148 KB	Output is correct
13	Correct	52 ms	16144 KB	Output is correct
14	Correct	44 ms	15960 KB	Output is correct
15	Correct	43 ms	15964 KB	Output is correct

Subtask #2

50.0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	57 ms	15964 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	452 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	68 ms	16172 KB	Output is correct
8	Correct	66 ms	15964 KB	Output is correct
9	Correct	168 ms	16168 KB	Output is correct
10	Correct	366 ms	16172 KB	Output is correct
11	Correct	66 ms	15960 KB	Output is correct
12	Correct	258 ms	15960 KB	Output is correct
13	Correct	53 ms	16172 KB	Output is correct
14	Correct	50 ms	15960 KB	Output is correct
15	Correct	47 ms	15960 KB	Output is correct