Submission #103654

#	Time	Username	Problem	Language	Result	Execution time	Memory
103654		igba	Watching (JOI13_watching)	C++17	50 / 100	161 ms	16476 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[1][0] = precalc[1][0], dp[0][1] = precalc[1][1];
	for(int i = 1; i <= p; ++i)
		for(int j = 1; j <= q; ++j)
			dp[i][j] = max(precalc[dp[i - 1][j]][0], 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:29: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:31: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: 0 / 50