답안 #1138

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1138	2013-06-27T12:38:30 Z	kriii	구경하기 (JOI13_watching)	C++	100 / 100	317 ms	16836 KB

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.0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	16836 KB	Output is correct
2	Correct	0 ms	16836 KB	Output is correct
3	Correct	0 ms	16836 KB	Output is correct
4	Correct	0 ms	16836 KB	Output is correct
5	Correct	0 ms	16836 KB	Output is correct
6	Correct	0 ms	16836 KB	Output is correct
7	Correct	0 ms	16836 KB	Output is correct
8	Correct	0 ms	16836 KB	Output is correct
9	Correct	0 ms	16836 KB	Output is correct
10	Correct	0 ms	16836 KB	Output is correct
11	Correct	0 ms	16836 KB	Output is correct
12	Correct	0 ms	16836 KB	Output is correct
13	Correct	0 ms	16836 KB	Output is correct
14	Correct	0 ms	16836 KB	Output is correct
15	Correct	0 ms	16836 KB	Output is correct

Subtask #2

50.0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	16836 KB	Output is correct
2	Correct	0 ms	16836 KB	Output is correct
3	Correct	0 ms	16836 KB	Output is correct
4	Correct	0 ms	16836 KB	Output is correct
5	Correct	0 ms	16836 KB	Output is correct
6	Correct	0 ms	16836 KB	Output is correct
7	Correct	5 ms	16836 KB	Output is correct
8	Correct	126 ms	16836 KB	Output is correct
9	Correct	23 ms	16836 KB	Output is correct
10	Correct	16 ms	16836 KB	Output is correct
11	Correct	317 ms	16836 KB	Output is correct
12	Correct	155 ms	16836 KB	Output is correct
13	Correct	5 ms	16836 KB	Output is correct
14	Correct	4 ms	16836 KB	Output is correct
15	Correct	6 ms	16836 KB	Output is correct