Submission #373330

#	Time	Username	Problem	Language	Result	Execution time	Memory
373330		antin_kuntin	Watching (JOI13_watching)	C++17	100 / 100	677 ms	32384 KiB

watching

#include <bits/stdc++.h>

using namespace std;

#define st first
#define nd second
#define pb push_back
#define int long long int
#define endl '\n'
#define MOD (int)(1e9 + 7)
#define eray chrono::steady_clock().now().time_since_epoch().count()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define mid start+(end-start)/2
#define debug(x) cerr << #x << " = " << x << endl
#define binary(x) cerr << #x << " = " << bitset<8>(x) << endl
#define N (int)(2e3)+5

int n, p, q, a;
vector<int> v;
int dp[N][N];
int precalc[N][2];

int rec(int wai, int lit){
	if(lit > p) return INT_MAX;
	if(wai >= n) return 0;
	if(~dp[wai][lit]) return dp[wai][lit];
	dp[wai][lit] = min(rec(precalc[wai][0]+1, lit+1), rec(precalc[wai][1]+1, lit)+1);
	return dp[wai][lit];
}

bool cont(int wai){
	memset(dp, -1, sizeof dp);
	for(int i = 0; i < n; i++){
		auto ka = lower_bound(all(v), v[i]+wai);
		auto sa = lower_bound(all(v), v[i]+wai*2);
		if(ka == v.end()) precalc[i][0] = n-1;
		else ka--, precalc[i][0] = ka-v.begin();
		if(sa == v.end()) precalc[i][1] = n-1;
		else sa--, precalc[i][1] = sa-v.begin();
	}
	if(rec(0, 0) > q) return false;
	return true;
}

int32_t main(){
	ios_base::sync_with_stdio(false);cin.tie(0); cout.tie(0);
	cin >> n >> p >> q;
	for(int i = 0; i < n; i++){
		cin >> a;
		v.pb(a);
	}
	sort(all(v));
	int start = 1, end = MOD, ans = INT_MAX;
	while(start <= end){
		if(cont(mid)) {ans = min(ans, mid); end = mid-1;}
		else start = mid+1;
	}
	cout << ans << endl;
}

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