oj.uz

Submission #373330

# Submission time Handle Problem Language Result Execution time Memory
373330 2021-03-04T06:52:09 Z antin_kuntin Watching (JOI13_watching) C++17
100 / 100
 677 ms 32384 KB 
#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.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 31980 KB Output is correct
2 Correct 133 ms 31852 KB Output is correct
3 Correct 136 ms 31852 KB Output is correct
4 Correct 134 ms 31980 KB Output is correct
5 Correct 130 ms 31852 KB Output is correct
6 Correct 134 ms 31852 KB Output is correct
7 Correct 138 ms 31852 KB Output is correct
8 Correct 134 ms 31852 KB Output is correct
9 Correct 137 ms 31852 KB Output is correct
10 Correct 133 ms 31852 KB Output is correct
11 Correct 139 ms 31756 KB Output is correct
12 Correct 140 ms 31852 KB Output is correct
13 Correct 139 ms 31852 KB Output is correct
14 Correct 141 ms 31852 KB Output is correct
15 Correct 139 ms 31852 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 31980 KB Output is correct
2 Correct 133 ms 31852 KB Output is correct
3 Correct 531 ms 32108 KB Output is correct
4 Correct 575 ms 31980 KB Output is correct
5 Correct 169 ms 31980 KB Output is correct
6 Correct 601 ms 31980 KB Output is correct
7 Correct 141 ms 31852 KB Output is correct
8 Correct 173 ms 31948 KB Output is correct
9 Correct 271 ms 32128 KB Output is correct
10 Correct 677 ms 32384 KB Output is correct
11 Correct 181 ms 31980 KB Output is correct
12 Correct 436 ms 32364 KB Output is correct
13 Correct 140 ms 31980 KB Output is correct
14 Correct 146 ms 31980 KB Output is correct
15 Correct 142 ms 31980 KB Output is correct