oj.uz

Submission #37757

# Submission time Handle Problem Language Result Execution time Memory
37757 2017-12-28T03:52:38 Z MatheusLealV Watching (JOI13_watching) C++14
100 / 100
 219 ms 18624 KB 
#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

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.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 18624 KB Output is correct
2 Correct 0 ms 18624 KB Output is correct
3 Correct 0 ms 18624 KB Output is correct
4 Correct 0 ms 18624 KB Output is correct
5 Correct 0 ms 18624 KB Output is correct
6 Correct 0 ms 18624 KB Output is correct
7 Correct 0 ms 18624 KB Output is correct
8 Correct 0 ms 18624 KB Output is correct
9 Correct 0 ms 18624 KB Output is correct
10 Correct 0 ms 18624 KB Output is correct
11 Correct 0 ms 18624 KB Output is correct
12 Correct 0 ms 18624 KB Output is correct
13 Correct 0 ms 18624 KB Output is correct
14 Correct 0 ms 18624 KB Output is correct
15 Correct 0 ms 18624 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18624 KB Output is correct
2 Correct 0 ms 18624 KB Output is correct
3 Correct 0 ms 18624 KB Output is correct
4 Correct 0 ms 18624 KB Output is correct
5 Correct 0 ms 18624 KB Output is correct
6 Correct 0 ms 18624 KB Output is correct
7 Correct 6 ms 18624 KB Output is correct
8 Correct 23 ms 18624 KB Output is correct
9 Correct 29 ms 18624 KB Output is correct
10 Correct 46 ms 18624 KB Output is correct
11 Correct 39 ms 18624 KB Output is correct
12 Correct 219 ms 18624 KB Output is correct
13 Correct 3 ms 18624 KB Output is correct
14 Correct 3 ms 18624 KB Output is correct
15 Correct 3 ms 18624 KB Output is correct