Submission #51471

#	Time	Username	Problem	Language	Result	Execution time	Memory
51471		MoesashiMinamoto	Watching (JOI13_watching)	C++14	100 / 100	137 ms	16380 KiB

watching

#include <bits/stdc++.h>

using namespace std;

int n, p, q;

int a[2003];
int dp[2003][2003];
int js[2003], jb[2003];

void jump(int w)
{
	for (int i = 0; i < n; i++)
	{
		js[i] = upper_bound(a, a+n, a[i]+w-1) - a;
		jb[i] = upper_bound(a, a+n, a[i]+2*w-1) - a;
	}
}

bool chec(int w)
{
	jump(w);
	memset(dp, -1, sizeof(dp));
	dp[0][0] = 0;
	for (int i = 0; i <= q; i++)
	{
		for (int j = 0; j <= p; j++)
		{
			if (dp[i][j] != -1)
			{
				if (dp[i][j] == n) return true;
				dp[i][j+1] = max(dp[i][j+1], js[dp[i][j]]);
				dp[i+1][j] = max(dp[i+1][j], jb[dp[i][j]]);
			}
		}
	}
	return false;
}

signed main()
{
	scanf("%d%d%d", &n, &p, &q);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &a[i]);
	}
	sort(a, a+n);
	if (p + q >= n) 
	{
		printf("1");
		return 0;
	}
	long long it = 0;
	for (int i = 33; i >= 0; i--)
	{
		if (it + (1ll << i) <= 1000000000)
		{
			long long cur = it + (1ll << i);
			if (!chec(cur))
			{
				it = cur;
			}
		}
	}
	printf("%lld", it+1);
}

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:45: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