Submission #230737

#	Time	Username	Problem	Language	Result	Execution time	Memory
230737		kshitij_sodani	Watching (JOI13_watching)	C++17	100 / 100	441 ms	16128 KiB

watching

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
//typedef int64_t llo;
#define mp make_pair
#define a first
#define b second
#define pb push_back
int it[2001];
int dp[2001][2001];
int n,p,q;
bool check(int mid){
	for(int i=0;i<p+1;i++){
		for(int j=0;j<q+1;j++){
			dp[i][j]=0;
		}
	}
	int pre[n];
	for(int i=0;i<n;i++){
		pre[i]=(int)(lower_bound(it,it+n,it[i]+mid)-it);
	}
	int pre2[n];
	for(int i=0;i<n;i++){
		pre2[i]=(int)(lower_bound(it,it+n,it[i]+2*mid)-it);
	}
	for(int i=0;i<p+1;i++){
		for(int j=0;j<q+1;j++){
			if(i==0 and j==0){
				continue;
			}
			if(i>0){
				if(dp[i-1][j]==n){
					dp[i][j]=n;
				}
				else{
					dp[i][j]=max(dp[i][j],pre[dp[i-1][j]]);
				}
			}
			if(j>0){
				if(dp[i][j-1]==n){
					dp[i][j]=n;
				}
				else{
					dp[i][j]=max(dp[i][j],pre2[dp[i][j-1]]);
				}
			}
		}
	}
	return dp[p][q]>=(n);
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>p>>q;
	for(int i=0;i<n;i++){
		cin>>it[i];
	}
	sort(it,it+n);
	p=min(p,n);
	q=min(q,n);
	int low=1;
	int high=1000000000;
	while(low<high-1){
		int mid=(low+high)/2;
		if(check(mid)){
			high=mid;
		}
		else{
			low=mid;
		}
	}
	int ans=high;
	if(check(low)){
		ans=min(ans,low);
	}
	cout<<ans<<endl;



	return 0;
}

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