Submission #299965

#	Time	Username	Problem	Language	Result	Execution time	Memory
299965		T0p_	Watching (JOI13_watching)	C++14	100 / 100	681 ms	11776 KiB

watching

#include<bits/stdc++.h>
using namespace std;

int n, p, q;
long long arr[2020], dp[2020][2020];

int EndPoint(int s, long long w)
{
	if(s > n) return n;
	int l = s, r = n;
	while(l != r)
	{
		int mid = (l+r+1)>>1;
		(arr[s] + w - 1 >= arr[mid]) ? l = mid : r = mid-1;
	}
	return l;
}

bool Test(long long w)
{
	for(int i=1 ; i<=p ; i++)
		dp[i][0] = EndPoint(dp[i-1][0]+1, w);
	for(int i=1 ; i<=q ; i++)
		dp[0][i] = EndPoint(dp[0][i-1]+1, w+w);
	for(int i=1 ; i<=p ; i++)
		for(int j=1 ; j<=q ; j++)
			dp[i][j] = max(EndPoint(dp[i-1][j]+1, w), EndPoint(dp[i][j-1]+1, w+w));
	return dp[p][q] == n;
}

int main()
{
	scanf(" %d %d %d",&n,&p,&q);
	for(int i=1 ; i<=n ; i++)
		scanf(" %lld",&arr[i]);
	sort(arr+1, arr+n+1);
	if(p+q >= n) printf("1\n");
	else
	{
		long long l = 1, r = 1e9;
		while(l != r)
		{
			long long mid = (l+r)>>1;
			(Test(mid)) ? r = mid : l = mid + 1;
		}
		printf("%lld\n",l);
	}
	return 0;
}

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |  scanf(" %d %d %d",&n,&p,&q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
watching.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   35 |   scanf(" %lld",&arr[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~

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