oj.uz

Submission #37687

# Submission time Handle Problem Language Result Execution time Memory
37687 2017-12-27T02:01:04 Z MatheusLealV Watching (JOI13_watching) C++14
50 / 100
 1000 ms 34932 KB 
#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

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

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

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2196 KB Output is correct
2 Correct 0 ms 2196 KB Output is correct
3 Correct 0 ms 2196 KB Output is correct
4 Correct 0 ms 2196 KB Output is correct
5 Correct 0 ms 2196 KB Output is correct
6 Correct 0 ms 2196 KB Output is correct
7 Correct 16 ms 2328 KB Output is correct
8 Execution timed out 1000 ms 34932 KB Execution timed out
9 Halted 0 ms 0 KB -