oj.uz

Submission #384233

# Submission time Handle Problem Language Result Execution time Memory
384233 2021-03-31T20:27:41 Z wind_reaper Watching (JOI13_watching) C++17
0 / 100
 135 ms 262148 KB 
#include <bits/stdc++.h>

using namespace std;
	
const int MXN = 2001;
const int MXP = 100001;
int dp[MXN][MXP], 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];

	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
0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 135 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 133 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -