Submission #154513

#	Time	Username	Problem	Language	Result	Execution time	Memory
154513		Lawliet	Watching (JOI13_watching)	C++14	100 / 100	189 ms	16120 KiB

watching

#include <bits/stdc++.h>

#define MAX 2010

using namespace std;

int n, p, q;

int v[MAX];
int dp[MAX][MAX];

bool test(int w)
{
	int indP = 1;
	int indQ = 1;

	for(int i = 1 ; i <= n ; i++)
	{
		while( v[i] - v[indQ] >= 2*w )
			indQ++;

		while( v[i] - v[indP] >= w )
			indP++;

		for(int j = 0 ; j <= p ; j++)
		{
			int& ans = dp[i][j];

			ans = dp[ indQ - 1 ][ j ] + 1;

			if(j > 0) ans = min(ans , dp[ indP - 1 ][ j - 1 ]);
		}
	}

	return dp[ n ][ p ] <= q;
}

int bs()
{
	int l = 1;
	int r = 1000000010;

	while(l < r)
	{
		int m = (l + r)/2;

		if( test(m) ) r = m;
		else l = m + 1;
	}

	return r;
}

int main()
{
	scanf("%d %d %d",&n,&p,&q);

	for(int i = 1 ; i <= n ; i++)
		scanf("%d",&v[i]);

	sort(v + 1 , v + n + 1);

	if(n <= p + q)
	{
		printf("1\n");
		return 0;
	}

	printf("%d\n",bs());
}

Compilation message (stderr)

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

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