Submission #1253281

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253281		cheetah	Watching (JOI13_watching)	C++20	100 / 100	161 ms	31860 KiB

watching

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cstdint>
//#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e9+7;
int n,k,b;  
int dp[2005][2005];
bool chick(int w,vector<int>&point){
	vector<int>u(n+1),v(n+1);
	for(int i=1;i<=n;i++){
		u[i]=upper_bound(point.begin()+1,point.end(),point[i]-w)-point.begin()-1;
		v[i]=upper_bound(point.begin()+1,point.end(),point[i]-2*w)-point.begin()-1;
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<=min(n,b);j++){
			if(j==0)dp[i][j]=dp[u[i]][j]+1;
			else dp[i][j]=min(dp[u[i]][j]+1,dp[v[i]][j-1]);
		}
	}
	return (dp[n][min(n,b)]<=k);
}
int32_t main(){  
	  
	int ans;
	cin>>n>>k>>b; 
	vector<int>point(n+1);
	for(int i=1;i<=n;i++)cin>>point[i];
	int l=1,r=N;
	sort(point.begin()+1,point.end());

    while(l<=r){
		int mid=(l+r)>>1;
		if(chick(mid,point)){
			ans=mid;
			r=mid-1;
		}
		else{
			l=mid+1;
		}
	}
	cout<<l<<endl;
}

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