제출 #872133

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
872133		serifefedartar	구경하기 (JOI13_watching)	C++17	100 / 100	366 ms	16984 KiB

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 / 50
• Subtask 2: 50 / 50