Submission #5115

#	Time	Username	Problem	Language	Result	Execution time	Memory
5115		cki86201	Watching (JOI13_watching)	C++98	100 / 100	280 ms	17048 KiB

watching

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

int P, Q, N, ans;
int w[2020];
int dp[2020][2020];
int prev[2020][2];

void pre(int x,int t)
{
	int i;
	for(i=1;i<=N&&w[i]-w[1]<x;i++)prev[i][t] = 1;
	for(int j=1;i<=N;i++){
		while(w[i]-w[j]>=x)j++;
		prev[i][t] = j;
	}
}

bool chk(int x)
{
	pre(x,0), pre(x<<1,1);
	int i, j;
	dp[0][0] = N+1;
	for(i=1;i<=P;i++)dp[i][0] = prev[dp[i-1][0]-1][0];
	for(i=1;i<=Q;i++)dp[0][i] = prev[dp[0][i-1]-1][1];
	for(i=1;i<=P;i++)
		for(j=1;j<=Q;j++)
			dp[i][j] = min(prev[dp[i-1][j]-1][0], prev[dp[i][j-1]-1][1]);
	return dp[P][Q] <= 1;
}

int main()
{
	scanf("%d%d%d",&N,&P,&Q);
	if(P+Q >= N)return printf("1")&0;
	for(int i=1;i<=N;i++)scanf("%d",w+i);
	sort(w+1,w+1+N);
	for(int s=1,e=1e9;s<=e;){
		int m = (s+e)>>1;
		if(chk(m))ans = m, e = m-1;
		else s = m+1;
	}
	printf("%d",ans);
	return 0;
}

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