oj.uz

Submission #384235

# Submission time Handle Problem Language Result Execution time Memory
384235 2021-03-31T20:37:22 Z wind_reaper Watching (JOI13_watching) C++17
50 / 100
 2 ms 1132 KB 
#include <bits/stdc++.h>

using namespace std;
	
const int MXN = 101;
const int MXP = 100001;
int dp[MXN][MXN], a[MXN];

int n, p, q;

bool check(int w){
	memset(dp, 0, sizeof dp);

	for(int i = 1; i <= n; i++){
		int l = 1, r = 1;
		while(a[i] - a[l] >= w) l++;
		while(a[i] - a[r] >= 2*w) r++;

		for(int j = 0; j <= p; j++)
			if(j == 0) dp[i][j] = dp[r-1][j] + 1;
			else dp[i][j] = min(dp[l-1][j-1], dp[r-1][j] + 1);
	}

	return dp[n][p] <= q;
}

int32_t main(){
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 
	
	cin >> n >> p >> q;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	p = min(p, n);
	sort(a+1, a+n+1);

	int lo = 1, hi = 1000000001;
	while(lo < hi){
		int mid = (lo + hi) >> 1;
		if(check(mid))
			hi = mid;
		else lo = mid + 1;
	}

	cout << lo << '\n';
	return 0; 
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 2 ms 364 KB Output is correct
12 Correct 2 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1132 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -