Submission #37764

#	Time	Username	Problem	Language	Result	Execution time	Memory
37764		MatheusLealV	Watching (JOI13_watching)	C++14	100 / 100	456 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;
}

int solve(int p, int q)
{
	if(!p && !q) return 1;

	if(dp[p][q] != -1) return dp[p][q];

	int ans = 1;

	if(p) ans = prox[ solve(p - 1, q) ][1];

	if(q) ans = max(ans, prox[solve(p, q - 1)][2]);

	return dp[p][q] = ans;
}

bool check(int w)
{
	memset(dp, -1, sizeof dp);
	
	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;

	return solve(A, B) > n;
}

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(check(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 check(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