Submission #364482

#	Time	Username	Problem	Language	Result	Execution time	Memory
364482		Rainbowbunny	Watching (JOI13_watching)	C++17	100 / 100	73 ms	8684 KiB

watching

#include <iostream>
#include <algorithm>

int n, p, q;
int a[2005], nextsmall[2005], nextlarge[2005], dp[2005][2005];

bool Check(int value)
{
	for(int i = 0; i < n; i++)
	{
		nextsmall[i] = std::upper_bound(a, a + n + 1, a[i] + value - 1) - a;
		nextlarge[i] = std::upper_bound(a, a + n + 1, a[i] + value * 2 - 1) - a;
	}
	for(int i = 0; i <= p; i++)
	{
		if(i > 0)
		{
			dp[i][0] = nextsmall[dp[i - 1][0]];
			if(dp[i][0] == n)
			{
				return true;
			}
		}
		else
		{
			dp[i][0] = 0;
		}
		for(int j = 1; j <= q; j++)
		{
			dp[i][j] = 0;
			if(i)
			{
				dp[i][j] = std::max(dp[i][j], nextsmall[dp[i - 1][j]]);
			}
			dp[i][j] = std::max(dp[i][j], nextlarge[dp[i][j - 1]]);
			if(dp[i][j] == n)
			{
				return true;
			}
		}
	}
	return false;
}

int main()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin >> n >> p >> q;
	p = std::min(p, n);
	q = std::min(q, n);
	for(int i = 0; i < n; i++)
	{
		std::cin >> a[i];
	}
	a[n] = 2e9;
	std::sort(a, a + n);	
	int l = 1, r = 1e9 / 2;
	while(l < r)
	{
		int mid = (l + r) >> 1;
		if(Check(mid))
		{
			r = mid;
		}
		else
		{
			l = mid + 1;
		}
	}
	std::cout << l;
}

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