Submission #1279045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279045		arashmemar	Watching (JOI13_watching)	C++20	100 / 100	701 ms	8680 KiB

watching

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e3 + 10;

int	a[maxn], dp[maxn][maxn], n, p, q;

int get(int x)
{
	return lower_bound(a + 1, a + 1 + n, x) - a;
}

bool check(int x)
{
	for (int i = 0;i <= p;i++)
	{
		for (int j = 0;j <= q;j++)
		{
			dp[i][j] = 1;
		}
	}
	for (int i = 0;i <= p;i++)
	{
		for (int j = 0;j <= q;j++)
		{
			if (i == 0 and j == 0)
			{
				continue;
			}
			if (i)
			{
				dp[i][j] = get(a[dp[i - 1][j]] + x);
			}
			if (j)
			{
				dp[i][j] = max(dp[i][j], get(a[dp[i][j - 1]] + 2 * x));
			}
			if (dp[i][j] == n + 1)
			{
				return 1;
			}
		}
	}
	return 0;
}

int main()
{
	cin >> n >> p >> q;
	if (p + q >= n)
	{
		cout << 1;
		return 0;
	}
	for (int i = 1;i <= n;i++)
	{
		cin >> a[i];
	}
	sort(a + 1, a + n + 1);
	a[n + 1] = 1e9 + 1;
	int l = 0, r = 1e9;
	while (r - l > 1)
	{
		int mid = (l + r) / 2;
		if (check(mid))
		{
			r = mid;
		}
		else
		{
			l = mid;
		}
	}
	cout << r;
}

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