oj.uz

답안 #759502

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
759502 2023-06-16T10:54:37 Z Fidan 구경하기 (JOI13_watching) C++17
100 / 100
 246 ms 31816 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
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));
vector<ll> qw1(N), qw2(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;
	}
	qw1[0]=-1;
	qw2[0]=-1;
	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){
		if(v[0]+w>v[i]){
			qw1[i]=-1;
		}
		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;
				}
			}
			qw1[i]=lo;
		}
	}
	rep(i, 1, n){
		if(v[0]+w>v[i]){
			qw2[i]=-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;
				}
			}
			qw2[i]=lo;
		}
	}
	rep(i, 1, n){
		rep(j, 1, p+1){
			dp[i][j]=N;
			if(qw1[i]==-1){
				dp[i][j]=0;
			}
			else{
				dp[i][j]=min(dp[i][j], dp[qw1[i]][j-1]);
			}
			if(qw2[i]==-1){
				dp[i][j]=min(dp[i][j], ll(1));
			}
			else{
				dp[i][j]=min(dp[i][j], dp[qw2[i]][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 14 ms 31700 KB Output is correct
2 Correct 17 ms 31780 KB Output is correct
3 Correct 16 ms 31744 KB Output is correct
4 Correct 16 ms 31740 KB Output is correct
5 Correct 16 ms 31780 KB Output is correct
6 Correct 14 ms 31780 KB Output is correct
7 Correct 14 ms 31732 KB Output is correct
8 Correct 14 ms 31692 KB Output is correct
9 Correct 14 ms 31672 KB Output is correct
10 Correct 13 ms 31700 KB Output is correct
11 Correct 15 ms 31764 KB Output is correct
12 Correct 13 ms 31784 KB Output is correct
13 Correct 13 ms 31780 KB Output is correct
14 Correct 14 ms 31772 KB Output is correct
15 Correct 13 ms 31700 KB Output is correct

Subtask #2
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 31748 KB Output is correct
2 Correct 14 ms 31700 KB Output is correct
3 Correct 14 ms 31700 KB Output is correct
4 Correct 14 ms 31816 KB Output is correct
5 Correct 14 ms 31700 KB Output is correct
6 Correct 16 ms 31724 KB Output is correct
7 Correct 20 ms 31800 KB Output is correct
8 Correct 32 ms 31796 KB Output is correct
9 Correct 106 ms 31808 KB Output is correct
10 Correct 246 ms 31792 KB Output is correct
11 Correct 27 ms 31700 KB Output is correct
12 Correct 132 ms 31804 KB Output is correct
13 Correct 17 ms 31784 KB Output is correct
14 Correct 19 ms 31700 KB Output is correct
15 Correct 19 ms 31700 KB Output is correct