oj.uz

Submission #987590

# Submission time Handle Problem Language Result Execution time Memory
987590 2024-05-23T06:38:26 Z hengliao Watching (JOI13_watching) C++17
0 / 100
 22 ms 31508 KB 
#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef long long ll;

const ll mxN=2005;
const ll inf=1e17;

ll n, p, q;

ll a[mxN];
ll dp[mxN][mxN];
ll o[mxN];
ll s[mxN];

bool check(ll tar){
	for(ll i=0;i<=n;i++){
		for(ll j=0;j<=p;j++){
			dp[i][j]=inf;
		}
	}
	for(ll i=0;i<=p;i++){
		dp[0][i]=0;
	}
	ll pt=0;
	for(ll i=0;i<n;i++){
		while(pt<n && a[pt]-a[i]+1<=tar){
			pt++;
		}
		o[i]=pt;
	}
	//cout<<"dumb "<<o[8]<<'\n';
	pt=0;
	for(ll i=0;i<n;i++){
		while(pt<n && a[pt]-a[i]+1<=2*tar){
			pt++;
		}
		s[i]=pt;
	}
	for(ll i=0;i<n;i++){
		for(ll j=0;j<=p;j++){
			//cout<<i<<' '<<j<<' '<<dp[i][j]<<'\n';
			// take small
			dp[o[i]][j]=min(dp[o[i]][j], dp[i][j]+1);
			//take big
			dp[s[i]][j+1]=min(dp[s[i]][j+1], dp[i][j]);
		}
	}
	//cout<<"checking "<<tar<<' '<<dp[n][p]<<'\n';
	//cout<<q<<' '<<(dp[n][p]<=q)<<'\n';
	return (dp[n][p]<=q);
}

void solve(){
	cin>>n>>p>>q;
	for(ll i=0;i<n;i++){
		cin>>a[i];
	}
	sort(a, a+n);
	/*for(ll i=0;i<n;i++){
		cout<<a[i]<<' ';
	}
	cout<<'\n';*/
	if(p+q>=n){
		cout<<1<<'\n';
		return;
	}

	ll ans;
	ll l=1, r=1e9+5;

	while(l<=r){
		ll mid=(l+r)/2;
		if(check(mid)){
			//cout<<mid<<" good\n";
			ans=mid;
			r=mid-1;
		}
		else{
			//cout<<mid<<" bad\n";
			l=mid+1;
		}
	}
	cout<<ans<<'\n';

	//check(8);
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	solve();
	return 0;
}

Subtask #1
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 500 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 428 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Incorrect 1 ms 2396 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31320 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 9 ms 31324 KB Output is correct
8 Incorrect 22 ms 31508 KB Output isn't correct
9 Halted 0 ms 0 KB -