oj.uz

답안 #758832

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
758832 2023-06-15T11:10:16 Z Fidan 구경하기 (JOI13_watching) C++17
50 / 100
 1000 ms 31868 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){
	rep(i, 0, N){
		rep(j, 0, N){
			dp[i][j]=N;
		}
	}
	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){
			// x es el mas grande index tal que v[x]+w<=v[i]
			// y es el mas grande index tal que v[y]+2*w<=v[i]
			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=(1e9)/3+2;
		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 97 ms 31744 KB Output is correct
2 Correct 14 ms 31700 KB Output is correct
3 Correct 96 ms 31740 KB Output is correct
4 Correct 15 ms 31700 KB Output is correct
5 Correct 15 ms 31700 KB Output is correct
6 Correct 16 ms 31716 KB Output is correct
7 Correct 102 ms 31740 KB Output is correct
8 Correct 104 ms 31868 KB Output is correct
9 Correct 107 ms 31700 KB Output is correct
10 Correct 103 ms 31756 KB Output is correct
11 Correct 108 ms 31752 KB Output is correct
12 Correct 101 ms 31740 KB Output is correct
13 Correct 109 ms 31748 KB Output is correct
14 Correct 100 ms 31736 KB Output is correct
15 Correct 103 ms 31700 KB Output is correct

Subtask #2
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 31708 KB Output is correct
2 Correct 15 ms 31700 KB Output is correct
3 Correct 15 ms 31728 KB Output is correct
4 Correct 15 ms 31700 KB Output is correct
5 Correct 16 ms 31700 KB Output is correct
6 Correct 17 ms 31700 KB Output is correct
7 Correct 127 ms 31756 KB Output is correct
8 Correct 234 ms 31764 KB Output is correct
9 Correct 886 ms 31748 KB Output is correct
10 Execution timed out 1068 ms 31700 KB Time limit exceeded
11 Halted 0 ms 0 KB -