Submission #37757

#	Time	Username	Problem	Language	Result	Execution time	Memory
37757		MatheusLealV	Watching (JOI13_watching)	C++14	100 / 100	219 ms	18624 KiB

watching

#include <bits/stdc++.h>
#define N 2050
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;

int n, p, q, v[N], dp[N][N], prox[N][3], A, B;

int prox_(int i, int w)
{
	int ini = i, fim = n, mid, best;

	while(fim >= ini)
	{
		mid = (ini + fim)/2;

		if(v[mid] - v[i] + 1 <= w) best = mid, ini = mid + 1;

		else fim = mid - 1;
	}

	return best + 1;
}

bool solve(int w)
{
	for(int i = 1; i <= n; i++) prox[i][1] = prox_(i, w), prox[i][2] = prox_(i, 2*w);

	prox[n + 1][1] = n + 1, prox[n + 1][2] = n + 1;

	for(int i = 0; i <= A; i++)
		for(int j = 0; j <= B; j++) dp[i][j] =1;

	for(int p = 0; p <= A ; p++)
	{
		for(int q = 0; q <= B; q++)
		{
			if(p) dp[p][q] = max(dp[p][q], prox[ dp[p - 1][q] ][1]);

			if(q) dp[p][q] = max(dp[p][q], prox[ dp[p][q - 1] ][2]);
		}
	}

	return dp[A][B] >= n + 1;
}

int32_t main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>n>>A>>B;

	for(int i = 1; i <= n; i++) cin>>v[i];

	if(A + B >= n)
	{
		cout<<"1\n";

		return 0;
	}

	sort(v + 1, v + n + 1);
	
	int ini = 1, fim = 1e9, mid, best = -1;

	while(fim >= ini)
	{
		mid = (ini + fim)/2;

		if(solve(mid)) best = mid, fim = mid - 1;

		else ini = mid + 1;
	}

	cout<<best<<'\n';
}

Compilation message (stderr)

watching.cpp: In function 'int prox_(int, int)':
watching.cpp:23:16: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return best + 1;
                ^
watching.cpp: In function 'bool solve(int)':
watching.cpp:23:16: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
watching.cpp:12:29: note: 'best' was declared here
  int ini = i, fim = n, mid, best;
                             ^
watching.cpp:23:16: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return best + 1;
                ^
watching.cpp:12:29: note: 'best' was declared here
  int ini = i, fim = n, mid, best;
                             ^

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