Submission #103743

#	Time	Username	Problem	Language	Result	Execution time	Memory
103743		igba	Watching (JOI13_watching)	C++17	100 / 100	246 ms	16396 KiB

watching

#include <bits/stdc++.h>
 
using namespace std;
const int MAXN = 2020, INF = 0x3f3f3f3f;
int n, p, q, a[MAXN], precalc[MAXN][2], dp[MAXN][MAXN];
 
bool ok(int w)
{
	for(int i = 1, j = 1; i <= n; ++i, j = i)
	{
		while(a[j] - a[i] < w && j <= n)
			j++;
		precalc[i][0] = j;
		while(a[j] - a[i] < 2 * w && j <= n)
			j++;
		precalc[i][1] = j;
	}
	precalc[n + 1][0] = precalc[n + 1][1] = n + 1;
	memset(dp, 0, sizeof dp);
	dp[0][0] = 1;
	for(int i = 0; i <= p; ++i)
		for(int j = 0; j <= q; ++j)
		{
			if(i >= 1)
				dp[i][j] = max(dp[i][j], precalc[dp[i - 1][j]][0]);
			if(j >= 1)
				dp[i][j] = max(dp[i][j], precalc[dp[i][j - 1]][1]);
		}
	return dp[p][q] > n;
}
 
int main()
{
	scanf("%d %d %d", &n, &p, &q);
	for(int i = 1; i <= n; ++i)
		scanf("%d", &a[i]);
	sort(a + 1, a + n + 1);
	if(p + q >= n)
		printf("1\n"), exit(0);
	int beg = 1, end = 1e9, mid;
	while(beg < end)
	{
		mid = (beg + end) >> 1;
		if(ok(mid))
			end = mid;
		else
			beg = mid + 1;
	}
	printf("%d\n", end);
}

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:34: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:36:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~

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