oj.uz

답안 #758835

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
758835 2023-06-15T11:11:49 Z Fidan 구경하기 (JOI13_watching) C++17
50 / 100
 1000 ms 31768 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for(ll i=ll(a); i<ll(b); i++)
#define repn(i, a, b) for(ll i=ll(b)-1; i>=ll(a); i--)
#define pb push_back
#define si size()
#define ff first
#define ss second
#define be begin()
#define en end()
const ll N=2002, P=2002;
vector<vector<ll>> dp(N, vector<ll> (P, N));
bool check(ll n, ll p, ll q, ll w, vector<ll> &v){
	dp[0][0]=1;
	rep(i, 1, p+1){
		dp[0][i]=0;
	}
	ll c=0;
	rep(i, 1, n){
		if(v[c]+2*w-1>=v[i]){
			dp[i][0]=dp[i-1][0];
		}
		else{
			c=i;
			dp[i][0]=dp[i-1][0]+1;
		}
	}
	rep(i, 1, n){
		rep(j, 1, p+1){
			dp[i][j]=N;
			if(v[0]+w>v[i]){
				dp[i][j]=0;
			}
			else{
				ll lo=0, hi=i-1;
				while(lo<hi){
					ll mid=(lo+hi+1)/2;
					if(v[mid]+w<=v[i]){
						lo=mid;
					}
					else{
						hi=mid-1;
					}
				}
				dp[i][j]=min(dp[i][j], dp[lo][j-1]);
			}
			if(v[0]+2*w>v[i]){
				dp[i][j]=min(dp[i][j], ll(1));
			}
			else{
				ll lo=0, hi=i-1;
				while(lo<hi){
					ll mid=(lo+hi+1)/2;
					if(v[mid]+2*w<=v[i]){
						lo=mid;
					}
					else{
						hi=mid-1;
					}
				}
				dp[i][j]=min(dp[i][j], dp[lo][j]+1);
			}
		}
	}
	if(dp[n-1][p]<=q){
		return true;
	}
	return false;
}
void solve(){
	ll n, p, q;
	cin>>n>>p>>q;
	vector<ll> v(n);
	rep(i, 0, n){
		cin>>v[i];
	}
	sort(v.be, v.en);
	if(p+q>=n){
		cout<<1;
	}
	else{
		ll lo=1, hi=v[n-1];
		while(lo<hi){
			ll mid=(lo+hi)/2;
			bool f=check(n, p, q, mid, v);
			if(f) hi=mid;
			else lo=mid+1;
		}
		cout<<hi;
	}
}
int main(){
	ios_base::sync_with_stdio();
	cin.tie(0);
	ll t=1;
	//~ cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

Subtask #1
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 31728 KB Output is correct
2 Correct 16 ms 31644 KB Output is correct
3 Correct 15 ms 31692 KB Output is correct
4 Correct 15 ms 31720 KB Output is correct
5 Correct 15 ms 31684 KB Output is correct
6 Correct 15 ms 31700 KB Output is correct
7 Correct 17 ms 31724 KB Output is correct
8 Correct 15 ms 31700 KB Output is correct
9 Correct 16 ms 31732 KB Output is correct
10 Correct 15 ms 31700 KB Output is correct
11 Correct 18 ms 31744 KB Output is correct
12 Correct 16 ms 31700 KB Output is correct
13 Correct 15 ms 31672 KB Output is correct
14 Correct 14 ms 31700 KB Output is correct
15 Correct 15 ms 31696 KB Output is correct

Subtask #2
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 31700 KB Output is correct
2 Correct 15 ms 31644 KB Output is correct
3 Correct 17 ms 31768 KB Output is correct
4 Correct 16 ms 31736 KB Output is correct
5 Correct 15 ms 31724 KB Output is correct
6 Correct 16 ms 31648 KB Output is correct
7 Correct 41 ms 31656 KB Output is correct
8 Correct 157 ms 31752 KB Output is correct
9 Correct 847 ms 31700 KB Output is correct
10 Execution timed out 1081 ms 31700 KB Time limit exceeded
11 Halted 0 ms 0 KB -