Submission #63505

#	Time	Username	Problem	Language	Result	Execution time	Memory
63505		njchung99	Watching (JOI13_watching)	C++14	100 / 100	236 ms	9028 KiB

watching

#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
ll x[2050];
int dp[2010][2010];
int nex[2010][2];
int main()
{
	int n, m, k;
	scanf("%d %d %d", &n, &m, &k);
	if (m + k >= n)
	{
		puts("1");
		return 0;
	}
	for (int i = 0; i < n; i++)
		scanf("%lld", &x[i]);
	sort(x, x + n);
	unique(x, x + n) - x;
	ll left = 1;
	ll right = 9999999999;
	ll dap = 1e15;
	while (left <= right)
	{
		ll mid = (left + right) / 2;
		nex[n][0] = n-1;
		nex[n][1] = n-1;
		for (int i = 0; i < n; i++)
		{
			nex[i][0] = lower_bound(x, x + n, x[i] + mid) - x-1;
			nex[i][1] = lower_bound(x, x + n, 2 * mid + x[i]) - x-1;
		}
		for (int i = 0; i <= m; i++)
		{
			for (int y = 0; y <= k; y++)
			{
				dp[i][y] = -1;
				if (i)dp[i][y] = max(dp[i][y], nex[dp[i - 1][y] + 1][0]);
				if (y)dp[i][y] = max(dp[i][y], nex[dp[i][y - 1] + 1][1]);
			}
		}
		if (dp[m][k] >= n - 1)
		{
			right = mid - 1;
			dap = min(dap, mid);
		}
		else {
			left = mid + 1;
		}
	}
	printf("%lld\n", dap);
}

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:20:19: warning: value computed is not used [-Wunused-value]
  unique(x, x + n) - x;
  ~~~~~~~~~~~~~~~~~^~~
watching.cpp:11:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &m, &k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:18:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &x[i]);
   ~~~~~^~~~~~~~~~~~~~~

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