Submission #1058735

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058735		ZeroCool	Watching (JOI13_watching)	C++14	100 / 100	181 ms	47760 KiB

watching

#include <bits/stdc++.h>

using namespace std;

#define ar array
#define int long long
#define ld long double
#define crash assert(69 == 420)

const int MOD = 1e9 + 7;
const int INF = 1e9;

const int N = 3000;
const int K = 300;
const int LOG = 30;

int n, p, q;

int A[N];
int dp[N][N];

bool check(int x){
	for(int i = 1;i <= n;i++){
		for(int j = 0;j <= p;j++){
			dp[i][j] = INF;
		}
	}
	for(int i = 1;i <= n;i++){
		int l = upper_bound(A + 1,A + n + 1, A[i] - x) - A;
		int r = upper_bound(A + 1, A + n + 1, A[i] - 2 * x) - A;
		for(int j = 0;j <= p;j++){
			if(j)dp[i][j] = min(dp[i][j], dp[l - 1][j - 1]);
			dp[i][j] = min(dp[i][j], dp[r - 1][j] + 1);
		}
	}
	for(int i = 0;i <= p;i++){
		if(dp[n][i] <= q)return 1;
	}
	return 0;
}

signed main(){ios_base::sync_with_stdio(false);cin.tie(0);
	cin>>n>>p>>q;
	for(int i =1 ;i <= n;i++)cin>>A[i];
	sort(A + 1, A + n  + 1);
	
	if(p + q >= n){
		cout<<1;
		return 0;
	}
	
	int ans = (1 << LOG) - 1;
	int tm = 1 << (LOG - 1);
	for(int i =0;i < LOG;i++){
		if(check(tm)){
			ans = tm;
			tm -= (tm & -tm) >> 1;
		}else tm += (tm & -tm)>>1;
	}
	cout<<ans;
}

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