제출 #1251788

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1251788		EkinOnal	구경하기 (JOI13_watching)	C++20	0 / 100	1093 ms	16272 KiB

watching

//#pragma GCC optimize("O3,unroll-loops,Ofast")
//#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
// using namespace __gnu_pbds;
 
#define MAX 200005
#define pb push_back
// #define mp make_pair 
// #define int long long
#define f first
#define s second
#define vi vector<int>
 
const int INF = 1e9+1;

	
	
void solve(){
	int n,p,q; cin>>n>>p>>q;
	vi v(n+5); for(int i=1;i<=n;i++) cin>>v[i];

	vi arr; for(int i=1;i<=n;i++) arr.pb(v[i]); 
	sort(arr.begin(),arr.end()); //arr.erase(unique(arr.begin(),arr.end()),arr.end());

	int l=1,r=1e9;
	while(l<r){
		int mid=(l+r)>>1;

		vector<vi> dp(n+5,vi(n+5,INF)); for(int i=0;i<=n;i++) dp[0][i]=0;
		for(int i=1;i<=n;i++){
			for(int j=0;j<=n;j++){
				int dist=v[i]-mid+1;

				int idx=lower_bound(arr.begin(),arr.end(),dist+1)-arr.begin();
				if(j) dp[i][j]=min(dp[i][j],dp[idx][j-1]);

				dist=v[i]-2*mid+1;
				idx=lower_bound(arr.begin(),arr.end(),dist+1)-arr.begin();
				dp[i][j]=min(dp[i][j],dp[idx][j]+1);
			}
		}
		
		int mn=0;
		for(int i=0;i<=n;i++){
			if(i<=p && dp[n][i]<=q) mn=1;
		}
		if(mn) r=mid;
		else l=mid+1;
	}	
	cout<<r<<endl;



}	
	
int32_t main(/*	int32_t argc, char* argv[]*/){
	std::ios_base::sync_with_stdio(0); std::cin.tie(0);	

	int t=1;
	// cin >> t;
	while (t--) solve();
 	
	return 0;
}	

• Subtask 1: 0 / 50
• Subtask 2: 0 / 50