답안 #1129

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1129	2013-06-26T08:17:29 Z	gs12117	구경하기 (JOI13_watching)	C++	100 / 100	105 ms	16692 KB

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

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

Subtask #2

50.0 / 50.0

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