Submission #51445

#	Time	Username	Problem	Language	Result	Execution time	Memory
51445		Vinhspm	Watching (JOI13_watching)	C++14	50 / 100	1078 ms	46636 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];
vector< vector<bool> > dp[N];
bool check(int x)	{
	// base
	for(int i = 0; i <= n; ++i)
		for(int j = 0; j <= P; ++j)
			for(int t = 0; t <= Q; ++t)
				dp[i][j][t] = false;
	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];
					}
					if(i == n && dp[i][j][t] == true) return true;
				}
	return false;
}
signed main()
{
	//freopen("test.txt", "r", stdin);
	//ios_base::sync_with_stdio(false);
	//cin.tie(0); cout.tie(0);
	scanf("%d%d%d", &n, &P, &Q);
	for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
	sort(a + 1, a + n + 1); a[0] = -oo;
	if(P + Q >= n) {
		printf("1");
		return 0;
	}
	for(int i = 0; i <= n + 1; ++i) {
		dp[i].resize(P + 10);
		for(int j = 0; j <= P + 1; ++j)	{
			for(int t = 0; t <= Q + 1; ++t)
				dp[i][j].pb(false);
		}
	}
	//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))	{
			printf("%d", i); 
			return 0;
		}
}

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &P, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
watching.cpp:44:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
                              ~~~~~^~~~~~~~~~~~~

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