Submission #1085325

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085325		4QT0R	Watching (JOI13_watching)	C++17	100 / 100	128 ms	31868 KiB

watching

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll eve[2003];
ll prv[2003];
ll prvdab[2003];
ll dp[2003][2003];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	ll n,p,q;
	cin >> n >> p >> q;
	for (ll i = 1; i<=n; i++)cin >> eve[i];
	sort(eve+1,eve+n+1);
	ll l=1,r=1e9,md;
	eve[0]=-1e9;
	while(l<r){
		md=(l+r)/2;
		ll iter=n;
		for (ll i = n; i>=1; i--){
			while(eve[i]-eve[iter]+1<=md)iter--;
			prv[i]=iter;
		}
		iter=n;
		for (ll i = n; i>=1; i--){
			while(eve[i]-eve[iter]+1<=2*md)iter--;
			prvdab[i]=iter;
		}
		for (ll i = 1; i<=n; i++){
			dp[i][0]=1+dp[prvdab[i]][0];
			for (ll j = 1; j<=min(n,p); j++){
				dp[i][j]=min(dp[prv[i]][j-1],1+dp[prvdab[i]][j]);
			}
		}
		bool ok=false;
		for (ll i = 1; i<=min(n,p); i++)if (dp[n][i]<=q)ok=true;
		if (ok)r=md;
		else l=md+1;
	}
	cout << l << '\n';
}

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