Submission #37687

#	Time	Username	Problem	Language	Result	Execution time	Memory
37687		MatheusLealV	Watching (JOI13_watching)	C++14	50 / 100	1000 ms	34932 KiB

watching

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

int n, p, q, v[N];

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;
}

struct ss
{
	int a, b, c;

	ss(int ai, int bi, int ci){ a = ai, b = bi, c = ci;}

	bool operator < (const ss &t) const
	{ 
		if(a != t.a) return a < t.a;

		if(b != t.b) return b < t.b;

		return c < t.c;
	 }
};

map< ss, bool > mapa; 

bool solve(int i, int p, int q, int w)
{
	if(i > n) return true;

	if(mapa.find({i, p, q}) != mapa.end()) return mapa[{i, p, q}];

	bool small = p ? solve(prox(i, w), p - 1, q, w) : 0;

	bool big = q ? solve(prox(i, 2*w), p, q - 1, w) : 0;

	return mapa[{i, p, q}] = small || big;
}

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

	cin>>n>>p>>q;

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

	if(p + q >= n)
	{
		cout<<"1\n";

		return 0;
	}

	sort(v + 1, v + n + 1);

	int ini = 0, fim = 1e9, mid, best = -1;

	while(fim >= ini)
	{
		mapa.clear();

		mid = (ini + fim)/2;

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

		else ini = mid + 1;
	}

	cout<<best<<"\n";
}

Compilation message (stderr)

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

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