Submission #1251803

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251803		EkinOnal	Watching (JOI13_watching)	C++20	100 / 100	311 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,lst=1;
	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++){
			int idx1=lower_bound(arr.begin(),arr.end(),arr[i-1]-mid+1)-arr.begin();
			int idx2=lower_bound(arr.begin(),arr.end(),arr[i-1]-2*mid+1)-arr.begin();

			for(int j=0;j<=n;j++){
				if(j) dp[i][j]=min(dp[i][j],dp[idx1][j-1]);

				dp[i][j]=min(dp[i][j],dp[idx2][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-1,lst=mid;
		else l=mid+1;
	}	
	cout<<lst<<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: 50 / 50
• Subtask 2: 50 / 50