제출 #156436

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
156436		Saboon	구경하기 (JOI13_watching)	C++14	100 / 100	187 ms	508 KiB

watching

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mod = 1e9 + 7;
const int maxn = 2e3 + 10;

int n, p, q, a[maxn];
int dp[2][maxn];
int nexlow[maxn], nexhig[maxn];

bool check(int w){
	for (int i = 0; i < n; i++){
		nexlow[i] = lower_bound(a, a + n, a[i] + w) - a - 1;
		nexhig[i] = lower_bound(a, a + n, a[i] + 2 * w) - a - 1;
	}
	nexlow[n] = nexhig[n] = n - 1;
	for (int i = 0; i <= p; i++){
		int x = i % 2;
		for (int j = 0; j <= q; j++){
			dp[x][j] = -1;
			if (i > 0)
				dp[x][j] = max(dp[x][j], nexlow[dp[1 - x][j] + 1]);
			if (j > 0)
				dp[x][j] = max(dp[x][j], nexhig[dp[x][j - 1] + 1]);
		}
	}
	return (dp[p%2][q] == n - 1);
}

int main(){
	ios_base::sync_with_stdio (false);
	cin >> n >> p >> q;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	sort(a, a + n);
	if (p + q >= n)
		return cout << 1 << endl, 0;
	int lo = 1, hi = 1000000000 + 1;
	while (hi - lo > 1){
		int mid = (lo + hi) >> 1;
		if (check(mid) == true)
			hi = mid;
		else
			lo = mid;
	}
	cout << hi << endl;
}

• Subtask 1: 50 / 50
• Subtask 2: 50 / 50