Submission #37684

#	Time	Username	Problem	Language	Result	Execution time	Memory
37684		MatheusLealV	Watching (JOI13_watching)	C++14	50 / 100	969 ms	124248 KiB

watching

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

int n, p, q, v[N], dp[N][N][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;
}

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

	if(dp[i][p][q] != -1) return dp[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 dp[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)
	{
		memset(dp, -1, sizeof dp);

		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 'bool solve(long long int, long long int, long long int, long long int)':
watching.cpp:37:32: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  return dp[i][p][q] = small || big;
                                ^
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