oj.uz

Submission #37764

# Submission time Handle Problem Language Result Execution time Memory
37764 2017-12-28T05:09:01 Z MatheusLealV Watching (JOI13_watching) C++14
100 / 100
 456 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;
}

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

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

# Verdict Execution time Memory Grader output
1 Correct 76 ms 18624 KB Output is correct
2 Correct 0 ms 18624 KB Output is correct
3 Correct 63 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 76 ms 18624 KB Output is correct
8 Correct 96 ms 18624 KB Output is correct
9 Correct 126 ms 18624 KB Output is correct
10 Correct 129 ms 18624 KB Output is correct
11 Correct 119 ms 18624 KB Output is correct
12 Correct 116 ms 18624 KB Output is correct
13 Correct 129 ms 18624 KB Output is correct
14 Correct 89 ms 18624 KB Output is correct
15 Correct 69 ms 18624 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 129 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 93 ms 18624 KB Output is correct
8 Correct 186 ms 18624 KB Output is correct
9 Correct 156 ms 18624 KB Output is correct
10 Correct 249 ms 18624 KB Output is correct
11 Correct 179 ms 18624 KB Output is correct
12 Correct 456 ms 18624 KB Output is correct
13 Correct 69 ms 18624 KB Output is correct
14 Correct 133 ms 18624 KB Output is correct
15 Correct 99 ms 18624 KB Output is correct