oj.uz

Submission #37684

# Submission time Handle Problem Language Result Execution time Memory
37684 2017-12-27T01:52:43 Z MatheusLealV Watching (JOI13_watching) C++14
50 / 100
 969 ms 124248 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 949 ms 124248 KB Output is correct
2 Correct 0 ms 124248 KB Output is correct
3 Correct 936 ms 124248 KB Output is correct
4 Correct 0 ms 124248 KB Output is correct
5 Correct 0 ms 124248 KB Output is correct
6 Correct 0 ms 124248 KB Output is correct
7 Correct 969 ms 124248 KB Output is correct
8 Correct 939 ms 124248 KB Output is correct
9 Correct 943 ms 124248 KB Output is correct
10 Correct 969 ms 124248 KB Output is correct
11 Correct 916 ms 124248 KB Output is correct
12 Correct 936 ms 124248 KB Output is correct
13 Correct 913 ms 124248 KB Output is correct
14 Correct 949 ms 124248 KB Output is correct
15 Correct 959 ms 124248 KB Output is correct

Subtask #2
0 / 50.0

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