Submission #1264712

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264712		nlsosad	Watching (JOI13_watching)	C++20	100 / 100	140 ms	31828 KiB

watching

#include <bits/stdc++.h>
#define int long long
using namespace std;
int inf = 1e18;
int a[2001];
int dp[2001][2001];
int cook(int w, int n, int p){
	for (int i = 0;i<=n;++i){
		for (int j = 0;j<=p;++j){
			dp[i][j] = inf;
		}
	}
	for (int i = 0;i<=p;++i){
		dp[0][i] = 0;
	}
	vector<int> ps(n+1, 0);
	vector<int> pl(n+1, 0);
	int l = 1, ll = 1;
	for (int i = 1;i<=n;++i){
		while(l<i and a[i]-a[l]>=w){
			l++;
		}
		while(ll<i and a[i]-a[ll]>=2*w){
			ll++;
		}
		ps[i] = l;
		pl[i] = ll;
	}
	/*for (int i = 1;i<=n;++i){
		cout << ps[i] << ' ';
	}
	cout << '\n';
	for (int i =1;i<=n;++i){
		cout << pl[i] << ' ';
	}
	cout << '\n';*/
	for (int i = 1;i<=n;++i){
		dp[i][0] = dp[pl[i]-1][0] +1;
		for (int j = 1;j<=p;++j){
			dp[i][j] = min(dp[ps[i]-1][j-1], dp[pl[i]-1][j]+1);
		}
	}
	return dp[n][p];
}
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, p, q;
	cin >> n >> p >> q;
	for (int i = 1;i<=n;++i){
		cin >> a[i];
	}
	sort(a+1, a+n+1);
	int l = 1, r = 1000000000;
	// int l = 14, r = 14;
	int res = 1;
	while(l<=r){
		int w = (l+r)/2;
		int t = cook(w, n, min(n, p));
		// cout << w << ' ' << t << '\n';
		if(t <= q){
			res = w;
			r = w-1;
		}else l = w+1;
	}
	cout << res;
}

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