Submission #520668

#	Time	Username	Problem	Language	Result	Execution time	Memory
520668		ymm	Watching (JOI13_watching)	C++17	100 / 100	116 ms	16080 KiB

watching

///
///   Oh? You're approaching me?
///

#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x)
#define LoopR(x,l,r) for(ll x = ll(r)-1; x >= ll(l); --x)
#define Kill(x) exit((cout << (x) << '\n', 0))
typedef long long ll;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
using namespace std;

const int N = 2010;
int dp[N][N];
int a[N];
int n, p, q;

void solve(int w){
	int p1=0, p2=0;
	Loop(i,0,n){
		while(a[i]-a[p1] >= w) ++p1;
		while(a[i]-a[p2] >= 2*w) ++p2;
		dp[i+1][0] = dp[p1][0]+1;
		Loop(k,1,q+1) dp[i+1][k] = min(dp[p1][k]+1, dp[p2][k-1]);
	}
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> p >> q;
	Loop(i,0,n) cin >> a[i];
	if(q>=n) Kill(1);
	sort(a,a+n);
	int l=1, r=1e9;
	while(l<r){
		int m = (l+r)/2;
		solve(m);
		if(dp[n][q] <= p) r=m;
		else              l=m+1;
	}
	cout << l << '\n';
}

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