Submission #370909

#	Time	Username	Problem	Language	Result	Execution time	Memory
370909		Yeboi	Watching (JOI13_watching)	C++14	100 / 100	363 ms	30188 KiB

watching

#include <bits/stdc++.h>
#define ll unsigned long long
#define mod 998244353
#define rep(i,s) for(ll i=0; i<s ; i++)
#define f(i,a,b) for(ll i(a); i<b ; i++)
#define inf -pow(10,9)
#define MAXN 100000 
const ll INF = 1000000000;
const ll N = 2005;
const ll modi = 1000000007;
const ll modi2= 1000000006;
using namespace std;

ll arr[N];

bool check(ll w , ll n, ll p , ll q){
	ll dp[n + 1][p + 1];
	rep(i,n){
		ll l = 0;
		ll r = 0;
		while(arr[i] - arr[l] >= w){
			l++;
		}
		while(arr[i] - arr[r] >= 2*w){
			r++;
		}

		rep(j , p + 1){
			if(j == 0){
				if(r == 0){
					dp[i][j] = 1;
				}
				else{
					dp[i][j] = dp[r-1][j] + 1;
				}
			}
			else{
				if(l == 0){
					dp[i][j] = 0;
				}
				else if(r == 0){
					dp[i][j] = min(dp[l-1][j-1], (ll)1);
				}
				else{
					dp[i][j] = min(dp[l-1][j-1], dp[r-1][j] + 1);
				}
			}
		}
	}
	if(dp[n-1][p] <= q){
		return true;
	}
	else{
		return false;
	}
}	

int main(){
	ll n,p,q;
	cin >> n >> p >> q;
	rep(i,n){
		cin >> arr[i];
	}
	sort(arr,arr+n);
	if(n <= p + q){
		cout << 1 << endl;
	}
	else{
		ll l = 1; ll r = 1000000010;
		while(l < r){
			ll mid = (l+r)/2;
			if(check(mid,n,p,q)){
				r = mid;
			}
			else{
				l = mid + 1;
			}
		}
		cout << l << endl;
	}
}

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