Submission #923732

#	Time	Username	Problem	Language	Result	Execution time	Memory
923732		Lalic	Watching (JOI13_watching)	C++17	100 / 100	529 ms	32156 KiB

watching

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define int long long

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5+10;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9+7;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, p, q;
vector<int> arr;

bool check(int w){
	vector<vector<int>> dp(n+1, vector<int>(p+1, INF));
	dp[0][0]=0;
	
	int ptr1=0, ptr2=0;
	for(int i=1;i<=n;i++){
		while(arr[ptr1+1]<=arr[i]-w) ptr1++;
		while(arr[ptr2+1]<=arr[i]-2*w) ptr2++;
		
		for(int j=0;j<=p;j++){
			if(j) dp[i][j]=min(dp[i][j], dp[ptr1][j-1]);
			dp[i][j]=min(dp[i][j], dp[ptr2][j]+1);
		}
	}
	
	int mn=INF;
	for(int i=0;i<=p;i++) mn=min(mn, dp[n][i]);
	
	return mn<=q;
}

void solve(){
	cin >> n >> p >> q; p=min(p, n);
	arr.resize(n+1); arr[0]=-INF;
	for(int i=1;i<=n;i++) cin >> arr[i];
	sort(arr.begin()+1, arr.end());
	
	int l=1, r=5e8, best=-1;
	while(l<=r){
		int mid=(l+r)>>1;
		if(check(mid)){
			best=mid;
			r=mid-1;
		}
		else l=mid+1;
	}
	
	cout << best << "\n";
}

int32_t main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
		
	int tt=1;
	//cin >> tt;
	while(tt--) solve();
	return 0;
}

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