Submission #1137

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137		kriii	Watching (JOI13_watching)	C++98	100 / 100	248 ms	17032 KiB

watching

#include <stdio.h>
#include <algorithm>
using namespace std;

int N,P,Q,A[2020];
int D[2020][2020];

bool chk(int w)
{
	if (w <= 0) return false;

	int i,j=1,k=1,l;
	for (i=1;i<=N;i++){
		while (A[i] - A[j] >= w) j++;
		while (A[i] - A[k] >= w * 2) k++;
		for (l=0;l<=Q;l++) D[i][l] = D[j-1][l] + 1;
		for (l=0;l<=Q;l++){
			if (D[i][l+1] > D[k-1][l])
				D[i][l+1] = D[k-1][l];
		}
	}

	for (l=0;l<=Q;l++) if (D[N][l] <= P) return true;
	return false;
}

int main()
{
	int i;

	scanf ("%d %d %d",&N,&P,&Q);
	for (i=1;i<=N;i++) scanf ("%d",&A[i]);
	sort(A+1,A+1+N);

	if (N <= P + Q) printf ("1");
	else{
		int l = 1, r = 1000000000, m;
		while (l < r){
			m = (l + r) / 2;
			if (chk(m)) r = m - 1;
			else l = m + 1;
		}
		while (chk(m)) m--;
		while (!chk(m)) m++;
		printf ("%d",m);
	}

	return 0;
}

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