Submission #1129

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129		gs12117	Watching (JOI13_watching)	C++98	100 / 100	105 ms	16692 KiB

watching

#include<stdio.h>
int n,p,q;
int a[2010];
int sc[2010];
int lc[2010];
int dp[2010][2010];
int f(long long int x){
	if(x<1)return 0;
	int i,j;
	j=0;
	for(i=0;i<n;i++){
		while(j<n&&a[j]-a[i]<x)j++;
		sc[i]=j;
	}
	sc[n]=n;
	j=0;
	for(i=0;i<n;i++){
		while(j<n&&a[j]-a[i]<x*2)j++;
		lc[i]=j;
	}
	lc[n]=n;
	for(i=0;i<=p;i++){
		for(j=0;j<=q;j++){
			dp[i][j]=-1;
		}
	}
	dp[0][0]=0;
	for(i=0;i<=p;i++){
		for(j=0;j<=q;j++){
			if(dp[i+1][j]<sc[dp[i][j]]){
				dp[i+1][j]=sc[dp[i][j]];
			}
			if(dp[i][j+1]<lc[dp[i][j]]){
				dp[i][j+1]=lc[dp[i][j]];
			}
		}
	}
	if(dp[p][q]==n)return 1;
	return 0;
}
int main(){
	long long int i,j,t;
	scanf("%d%d%d",&n,&p,&q);
	for(i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	if(n<=p+q){
		printf("1");
		return 0;
	}
	for(i=0;i<n;i++){
		for(j=0;j<i;j++){
			if(a[j]>a[i]){
				t=a[i];
				a[i]=a[j];
				a[j]=t;
			}
		}
	}
	j=-1;
	for(i=32;i>=0;i--){
		j+=1LL<<i;
		if(f(j)==1)j-=1LL<<i;
	}
	j++;
	printf("%lld",j);
}

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