Submission #948181

#	Time	Username	Problem	Language	Result	Execution time	Memory
948181		amirhoseinfar1385	Watching (JOI13_watching)	C++17	100 / 100	188 ms	16168 KiB

watching

#include<bits/stdc++.h>
using namespace std;
const int maxn=2005;
int n,a,b,all[maxn],dp[maxn][maxn];

void vorod(){
	cin>>n>>a>>b;
	a=min(n,a);
	b=min(n,b);
	for(int i=1;i<=n;i++){
		cin>>all[i];
	}
	sort(all+1,all+n+1);
}

int check(int len){
	for(int i=1;i<=n;i++){
		int l1=0,l2=0;
		while(l1+1<i&&all[i]-all[l1+1]+1>len*2){
			l1++;
		}
		while(l2+1<i&&all[i]-all[l2+1]+1>len){
			l2++;
		}
		for(int j=0;j<=a;j++){
			dp[i][j]=dp[l1][j]+1;
			if(j>0){
				dp[i][j]=min(dp[i][j],dp[l2][j-1]);
			}
			//cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
		}
	}
	return dp[n][a]<=b;
}

void solve(){
	int low=0,high=2e9+1,mid;
	while(high-low>1){
		mid=(high+low)>>1;
		if(check(mid)){
			high=mid;
		}else{
			low=mid;
		}
	}
	cout<<high<<"\n";
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
//	freopen("inp.txt","r",stdin);
	vorod();
	solve();
}

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