제출 #51436

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
51436		Vinhspm	Watching (JOI13_watching)	C++14	50 / 100	1064 ms	38176 KiB

watching

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<int, int>
#define fi first
#define se second
#define pb push_back
const int N = 2009;
const int oo = 1e9;
const int mod = 1e9 + 7;
int n, P, Q;
int a[N];
bool check(int x)	{
	vector< vector<bool> > dp[N];
	for(int i = 0; i <= n; ++i) {
		dp[i].resize(P + 5);
		for(int j = 0; j <= P; ++j)	{
			dp[i][j].assign(Q + 5, false);
		}
	}
	// base
	dp[0][P][Q] = true;
	for(int i = 1; i <= n; ++i)
		for(int j = 0; j <= P; ++j)
			for(int t = 0; t <= Q ;++t)	{
					if(j < P) 	{
						int nexpos = a[i] - x + 1;
						int pos = lower_bound(a + 1, a + n + 1, nexpos) - a - 1;
						dp[i][j][t] = dp[pos][j + 1][t];
					}
					if(t < Q && dp[i][j][t] == false)	{
						int nexpos = a[i] - 2*x + 1;
						int pos = lower_bound(a + 1, a + n + 1, nexpos) - a - 1;
						dp[i][j][t] = dp[pos][j][t + 1];
					}
				} 
	for(int j = 0; j <= P; ++j)
			for(int t = 0; t <= Q ;++t)
				if(dp[n][j][t])	
					return true;
	return false;
}
signed main()
{
	//freopen("test.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> P >> Q;
	for(int i = 1; i <= n; ++i) cin >> a[i];
	sort(a + 1, a + n + 1); a[0] = -oo;
	if(P + Q >= n) {
		cout << "1";
		return 0;
	}
	//cout << check(3) << '\n'; return 0;
	int l = 1, r = oo;
	while(r > l + 1)	{
		int mid = (l + r)/ 2;
		if(check(mid)) r = mid;
		else l = mid;
	}
	for(int i = l; i <= r; ++i)
		if(check(i))	{
			cout << i; return 0;
		}
}

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