Submission #51451

#	Time	Username	Problem	Language	Result	Execution time	Memory
51451		Vinhspm	Watching (JOI13_watching)	C++14	100 / 100	109 ms	8868 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], dp[N][N], calc[N][2];
bool check(int x)	{
	// base
	for(int i = 0; i <= n; ++i)	{
		calc[i][0] = upper_bound(a + 1, a + n + 1, a[i] + x - 1) - a - 1;
		calc[i][1] = upper_bound(a + 1, a + n + 1, a[i] + 2*x - 1) - a - 1;
	}
	for(int i = 0; i <= P; ++ i)
		for(int j = 0; j <= Q; ++j)
			dp[i][j] = -1;
	dp[0][0] = 0;
	for(int i = 0; i <= P; ++i)
		for(int j = 0; j <= Q; ++j){
				if(i > 0)	{
					int cur = dp[i - 1][j] + 1;
					dp[i][j] = max(dp[i][j], calc[cur][0]);
				}
				if(j > 0)	{
					int cur = dp[i][j - 1] + 1;
					dp[i][j] = max(dp[i][j], calc[cur][1]);
				}
				if(dp[i][j] == n) 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] = 0;
	if(P + Q >= n) {
		printf("1");
		return 0;
	}
	//cout << check(3) << '\n'; return 0;
	int l = 1, r = 1e9;
	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:42: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:43: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: 50 / 50