제출 #759502

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
759502		Fidan	Watching (JOI13_watching)	C++17	100 / 100	246 ms	31816 KiB

watching

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
typedef long long ll;
#define rep(i, a, b) for(ll i=ll(a); i<ll(b); i++)
#define repn(i, a, b) for(ll i=ll(b)-1; i>=ll(a); i--)
#define pb push_back
#define si size()
#define ff first
#define ss second
#define be begin()
#define en end()
const ll N=2002, P=2002;
vector<vector<ll>> dp(N, vector<ll> (P, N));
vector<ll> qw1(N), qw2(N);
bool check(ll n, ll p, ll q, ll w, vector<ll> &v){
	dp[0][0]=1;
	rep(i, 1, p+1){
		dp[0][i]=0;
	}
	qw1[0]=-1;
	qw2[0]=-1;
	ll c=0;
	rep(i, 1, n){
		if(v[c]+2*w-1>=v[i]){
			dp[i][0]=dp[i-1][0];
		}
		else{
			c=i;
			dp[i][0]=dp[i-1][0]+1;
		}
	}
	rep(i, 1, n){
		if(v[0]+w>v[i]){
			qw1[i]=-1;
		}
		else{
			ll lo=0, hi=i-1;
			while(lo<hi){
				ll mid=(lo+hi+1)/2;
				if(v[mid]+w<=v[i]){
					lo=mid;
				}
				else{
					hi=mid-1;
				}
			}
			qw1[i]=lo;
		}
	}
	rep(i, 1, n){
		if(v[0]+w>v[i]){
			qw2[i]=-1;
		}
		else{
			ll lo=0, hi=i-1;
			while(lo<hi){
				ll mid=(lo+hi+1)/2;
				if(v[mid]+2*w<=v[i]){
					lo=mid;
				}
				else{
					hi=mid-1;
				}
			}
			qw2[i]=lo;
		}
	}
	rep(i, 1, n){
		rep(j, 1, p+1){
			dp[i][j]=N;
			if(qw1[i]==-1){
				dp[i][j]=0;
			}
			else{
				dp[i][j]=min(dp[i][j], dp[qw1[i]][j-1]);
			}
			if(qw2[i]==-1){
				dp[i][j]=min(dp[i][j], ll(1));
			}
			else{
				dp[i][j]=min(dp[i][j], dp[qw2[i]][j]+1);
			}
		}
	}
	if(dp[n-1][p]<=q){
		return true;
	}
	return false;
}
void solve(){
	ll n, p, q;
	cin>>n>>p>>q;
	vector<ll> v(n);
	rep(i, 0, n){
		cin>>v[i];
	}
	sort(v.be, v.en);
	if(p+q>=n){
		cout<<1;
	}
	else{
		ll lo=1, hi=v[n-1];
		while(lo<hi){
			ll mid=(lo+hi)/2;
			bool f=check(n, p, q, mid, v);
			if(f) hi=mid;
			else lo=mid+1;
		}
		cout<<hi;
	}
}
int main(){
	ios_base::sync_with_stdio();
	cin.tie(0);
	ll t=1;
	//~ cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

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