제출 #1291052

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1291052		haha	Watching (JOI13_watching)	C++20	100 / 100	68 ms	16168 KiB

watching

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=2e3+5;

int n,a,b;
int h[maxn],r[maxn],r2[maxn];
int dp[maxn][maxn];

bool check(int w){
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=n;i++){
		r[i]=upper_bound(h+1,h+n+1,h[i]+w-1)-h-1;
		r2[i]=upper_bound(h+1,h+n+1,h[i]+2*w-1)-h-1;
	}
	dp[0][0]=0;
	for(int i=0;i<=a;i++){
		for(int j=0;j<=b;j++){
			if(i==0&&j==0) continue;
			if(i>0) dp[i][j]=max(dp[i][j],r[dp[i-1][j]+1]);
			if(j>0) dp[i][j]=max(dp[i][j],r2[dp[i][j-1]+1]);
			if(dp[i][j]>=n) return true;
		}
	}
	if(dp[a][b]==n) return true;
	return false;
}

int main(){
	cin>>n>>a>>b;
	for(int i=1;i<=n;i++) cin>>h[i];
	if(a+b>=n){
		cout<<1;
		return 0;
	}
	sort(h+1,h+n+1);
	int l=1,r=1e9,ans=0;
	while(l<=r){
		int m=(l+r)/2;
		if(check(m)){
			ans=m;
			r=m-1;
		}
		else l=m+1;
	}
	cout<<ans;
}

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