Submission #547128

#	Time	Username	Problem	Language	Result	Execution time	Memory
547128		Hanksburger	Watching (JOI13_watching)	C++17	100 / 100	99 ms	14284 KiB

watching

#include <bits/stdc++.h>
using namespace std;
int dp[2005][2005], a[2005];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, p, q, l=1, r=1e9;
	cin >> n >> p >> q;
	p=min(p, n);
	for (int i=1; i<=n; i++)
		cin >> a[i];
	sort(a+1, a+n+1);
	while (l<r)
	{
		int mid=(l+r)/2;
		for (int i=1; i<=n; i++)
		{
			int x=upper_bound(a+1, a+n+1, a[i]-mid)-a-1, y=upper_bound(a+1, a+n+1, a[i]-mid*2)-a-1;
			for (int j=0; j<=i; j++)
			{
				dp[i][j]=dp[y][j]+1;
				if (j)
					dp[i][j]=min(dp[i][j], dp[x][j-1]);
			}
		}
		if (dp[n][p]>q)
			l=mid+1;
		else
			r=mid;
	}
	cout << l;
	return 0;
}

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