oj.uz

Submission #236172

# Submission time Handle Problem Language Result Execution time Memory
236172 2020-05-31T10:42:42 Z ernestvw Watching (JOI13_watching) C++11
50 / 100
 33 ms 16896 KB 
/*
	* ernestvw
	* C++
	* May 2020
*/

#include <bits/stdc++.h>
using namespace std;

#define int long long

#define x first
#define y second
#define pb push_back
#define pii pair<int, int>
#define veci vector<int>
#define vecs vector<string>
#define amax(x, v) x = max(x, (v))
#define amin(x, v) x = min(x, (v))
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define sz(v) (int)(v.size())
#define FOR(i, n) for(int i = 0; i < (n); ++i)
#define nl '\n'

using ll = long long;
using ld = long double;
using ull = unsigned long long;
template <class T>
using PQ = priority_queue<T, vector<T>, greater<T>>;

const int oo = 1e9; // INT_MAX
const long long OO = 1e18; // LLONG_MAX
const double eps = 1e-9;
const double pi = 4.0 * atan(1.0);
const int p197 = 1000000007;
const int p998 = 998244353;
const int p103 = 1000003;

#define TEST_CASES 0

void solve(int test_case);

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int T = 1;
	if(TEST_CASES) cin >> T;
	for(int t = 1; t <= T; t++)
		solve(t);

	return 0;
}

// ---------------------------------------------------

int n, p, q;
veci a;

int dp[101][101][101];
int W = 1;

int f(int i, int P, int Q) {
	if(i < n && P == 0 && Q == 0) {
		return 0;
	}
	if(i == n) return 1;
	if(dp[i][P][Q] != -1) return dp[i][P][Q];
	dp[i][P][Q] = 0;
	if(P > 0) {
		int j = i;
		while(j < n && a[j] - a[i] + 1LL <= W) j++;
		dp[i][P][Q] |= f(j, P-1, Q);
	}
	if(Q > 0) {
		int j = i;
		while(j < n && a[j] - a[i] + 1LL <= 2LL * W) j++;
		dp[i][P][Q] |= f(j, P, Q-1);
	}
	return dp[i][P][Q];
}

bool possible(int w) {
	W = w;
	memset(dp, -1, sizeof(dp));
	return bool(f(0, p, q));
}

void solve(int test_case) {
	cin >> n >> p >> q;
	a.resize(n);
	FOR(i, n) cin >> a[i];
	sort(all(a));
	amin(p, n), amin(q, n);
	int w = 1e9;
	for(int j = 31; j >= 0; j--) {
		if(w - (1LL << j) >= 0 && possible(w - (1LL << j))) {
			w -= (1LL << j);
		}
	}
	cout << w << endl;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 8448 KB Output is correct
2 Correct 21 ms 8448 KB Output is correct
3 Correct 25 ms 8448 KB Output is correct
4 Correct 26 ms 8448 KB Output is correct
5 Correct 24 ms 8448 KB Output is correct
6 Correct 24 ms 8448 KB Output is correct
7 Correct 29 ms 8448 KB Output is correct
8 Correct 31 ms 8448 KB Output is correct
9 Correct 29 ms 8448 KB Output is correct
10 Correct 33 ms 8448 KB Output is correct
11 Correct 32 ms 8448 KB Output is correct
12 Correct 23 ms 8448 KB Output is correct
13 Correct 25 ms 8448 KB Output is correct
14 Correct 31 ms 8448 KB Output is correct
15 Correct 26 ms 8576 KB Output is correct

Subtask #2
0 / 50.0

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