Submission #987597

#	Time	Username	Problem	Language	Result	Execution time	Memory
987597		hengliao	Watching (JOI13_watching)	C++17	100 / 100	283 ms	31912 KiB

watching

#include<bits/stdc++.h>
using namespace std;
 
#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef long long ll;
 
const ll mxN=2005;
const ll inf=1e17;
 
ll n, p, q;
 
ll a[mxN];
ll dp[mxN][mxN];
ll o[mxN];
ll s[mxN];
 
bool check(ll tar){
	for(ll i=0;i<=n;i++){
		for(ll j=0;j<=p;j++){
			dp[i][j]=inf;
		}
	}
	for(ll i=0;i<=p;i++){
		dp[0][i]=0;
	}
	ll pt=0;
	for(ll i=0;i<n;i++){
		while(pt<n && a[pt]-a[i]+1<=tar){
			pt++;
		}
		o[i]=pt;
	}
	//cout<<"dumb "<<o[8]<<'\n';
	pt=0;
	for(ll i=0;i<n;i++){
		while(pt<n && a[pt]-a[i]+1<=2*tar){
			pt++;
		}
		s[i]=pt;
	}
	for(ll i=0;i<n;i++){
		for(ll j=0;j<=p;j++){
			//cout<<i<<' '<<j<<' '<<dp[i][j]<<'\n';
			// take small
			dp[o[i]][j]=min(dp[o[i]][j], dp[i][j]+1);
			//take big
			dp[s[i]][j+1]=min(dp[s[i]][j+1], dp[i][j]);
		}
	}
	//cout<<"checking "<<tar<<' '<<dp[n][p]<<'\n';
	//cout<<q<<' '<<(dp[n][p]<=q)<<'\n';
	return (dp[n][p]<=q);
}
 
void solve(){
	cin>>n>>q>>p;
	for(ll i=0;i<n;i++){
		cin>>a[i];
	}
	sort(a, a+n);
	/*for(ll i=0;i<n;i++){
		cout<<a[i]<<' ';
	}
	cout<<'\n';*/
	if(p+q>=n){
		cout<<1<<'\n';
		return;
	}
 
	ll ans;
	ll l=1, r=1e9+5;
 
	while(l<=r){
		ll mid=(l+r)/2;
		if(check(mid)){
			//cout<<mid<<" good\n";
			ans=mid;
			r=mid-1;
		}
		else{
			//cout<<mid<<" bad\n";
			l=mid+1;
		}
	}
	cout<<ans<<'\n';
 
	//check(8);
}
 
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
 
	solve();
	return 0;
}

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