oj.uz

Submission #822603

# Submission time Handle Problem Language Result Execution time Memory
822603 2023-08-12T04:02:10 Z vjudge1 Watching (JOI13_watching) C++17
0 / 100
 154 ms 31804 KB 
#include <bits/stdc++.h>
#define ll long long
#define sp << " "
#define faster ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
ll n, p, q, a[2005], dp[2005][2005], k, l;

bool check(ll mid){
	memset(dp,0x3f,sizeof(dp));
	dp[0][0]=0;
	k=1,l=1;
	for(ll i = 1; i <= n; i++){
		while(a[i]-a[k]>mid) k++;
		while(a[i]-a[l]>2*mid) l++;
		for(ll j = 0; j <= q; j++){
			dp[i][j]=dp[k-1][j]+1;
			if(j>0) dp[i][j]=min(dp[i][j],dp[l-1][j-1]);
		}
	}
	for(ll i = 0; i <= q; i++) if(dp[n][i]<=p) return true;
	return false; 
}
int main(){
    faster;
    cin >> n >> p >> q;
    for(ll i = 1; i <= n; i++) cin >> a[i];
    sort(a+1,a+n+1);
    if(p>=n||q>=n){
    	cout << 1;
    	return 0;
    }
    ll l = 1, r = 1e15, mid;
    while(l<=r){
    	mid=(l+r)/2;
    	if(!check(mid)) l=mid+1;
    	else r=mid-1;
    }
    cout << l+1;
    return 0;
}

Subtask #1
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 31780 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Incorrect 144 ms 31780 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 31804 KB Output is correct
2 Incorrect 154 ms 31776 KB Output isn't correct
3 Halted 0 ms 0 KB -