Submission #239500

#	Time	Username	Problem	Language	Result	Execution time	Memory
239500		frodakcin	Watching (JOI13_watching)	C++11	100 / 100	109 ms	16248 KiB

watching

#include <cstdio>
#include <cstring>
#include <algorithm>

template<typename T> bool ckmax(T& a, T b){return a<b?a=b,1:0;}
template<typename T> bool ckmin(T& a, T b){return a>b?a=b,1:0;}

const int MN = 2e3+10;
int N, P, Q, dp[MN][MN], a[MN], nex[MN][2];

bool test(int w)
{
	nex[N][0] = nex[N][1] = 0;
	for(int i=0;i<N;++i)//can be optimized from O(N log N) to O(N) but it isnt bottleneck
	{
		nex[i][0] = std::lower_bound(a, a+N, a[i]+w  )-a;
		nex[i][1] = std::lower_bound(a, a+N, a[i]+w*2)-a;
	}
	memset(dp, -1, sizeof dp);
	dp[0][0]=0;
	for(int i=0;i<=P;++i)
		for(int j=0;j<=Q;++j)
			if(~dp[i][j])
			{
				int x=dp[i][j];
				if(x==N) return 1;
				if(i<P) ckmax(dp[i+1][j], nex[x][0]);
				if(j<Q) ckmax(dp[i][j+1], nex[x][1]);
			}
	return 0;
}
int main()
{
	scanf("%d%d%d", &N, &P, &Q);
	for(int i=0;i<N;++i) scanf("%d", a+i);
	std::sort(a, a+N);
	if(P+Q>=N) return printf("1\n"),0;
	int l=0,r=1e9,m;
	for(;r-l>1;)
	{
		m=l+(r-l)/2;
		if(test(m))
			r=m;
		else
			l=m;
	}
	printf("%d\n", r);
	return 0;
}

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:34: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:35:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0;i<N;++i) scanf("%d", a+i);
                       ~~~~~^~~~~~~~~~~

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