Submission #1278345

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278345		arashmemar	Watching (JOI13_watching)	C++20	50 / 100	1095 ms	8688 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);
}

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

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: 0 / 50