oj.uz

Submission #37681

# Submission time Handle Problem Language Result Execution time Memory
37681 2017-12-27T01:37:22 Z MatheusLealV Watching (JOI13_watching) C++14
0 / 100
 473 ms 63212 KB 
#include <bits/stdc++.h>
#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;
}

int 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, 1, mid)) best = mid, fim = mid - 1;

		else ini = mid + 1;
	}

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

Compilation message

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

# Verdict Execution time Memory Grader output
1 Correct 473 ms 63212 KB Output is correct
2 Correct 0 ms 63212 KB Output is correct
3 Incorrect 453 ms 63212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 63212 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -