oj.uz

Submission #822613

# Submission time Handle Problem Language Result Execution time Memory
822613 2023-08-12T04:04:22 Z vjudge1 Watching (JOI13_watching) C++17
100 / 100
 346 ms 31828 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,63,sizeof(dp));
	dp[0][0]=0;
	k=1,l=1;
	for(ll i = 1; i <= n; i++){
		while(a[i]-a[k]+1>mid) k++;
		while(a[i]-a[l]+1>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;
    return 0;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 31784 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 150 ms 31772 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 135 ms 31800 KB Output is correct
8 Correct 138 ms 31780 KB Output is correct
9 Correct 138 ms 31780 KB Output is correct
10 Correct 143 ms 31780 KB Output is correct
11 Correct 144 ms 31784 KB Output is correct
12 Correct 153 ms 31780 KB Output is correct
13 Correct 141 ms 31784 KB Output is correct
14 Correct 146 ms 31788 KB Output is correct
15 Correct 154 ms 31700 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 31808 KB Output is correct
2 Correct 141 ms 31772 KB Output is correct
3 Correct 316 ms 31808 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 137 ms 31808 KB Output is correct
8 Correct 274 ms 31808 KB Output is correct
9 Correct 182 ms 31812 KB Output is correct
10 Correct 143 ms 31804 KB Output is correct
11 Correct 346 ms 31808 KB Output is correct
12 Correct 291 ms 31808 KB Output is correct
13 Correct 151 ms 31812 KB Output is correct
14 Correct 141 ms 31808 KB Output is correct
15 Correct 148 ms 31828 KB Output is correct