Submission #1138

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138		kriii	Watching (JOI13_watching)	C++98	100 / 100	317 ms	16836 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,k,l;
	for (i=j=k=1;i<=N;i++){
		while (A[i] - A[j] >= w) j++;
		while (A[i] - A[k] >= w * 2) k++;

		D[i][0] = D[j-1][0] + 1;
		for (l=1;l<=Q;l++) D[i][l] = min(D[j-1][l] + 1, D[k-1][l-1]);
	}

	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