oj.uz

Submission #236175

# Submission time Handle Problem Language Result Execution time Memory
236175 2020-05-31T11:44:29 Z ernestvw Watching (JOI13_watching) C++11
100 / 100
 98 ms 12024 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[2001][2001];
int prochain[2001], prochain2[2001];

bool possible(int w) {
	int p1 = 0, p2 = 0;
	FOR(i, n) {
		while(p1 < n && a[p1] - a[i] + 1LL <= w) p1++;
		while(p2 < n && a[p2] - a[i] + 1LL <= 2LL * w) p2++;
		prochain[i] = p1;
		prochain2[i] = p2;
	}
	FOR(i,p+1)FOR(j,q+1){
		if(i==0 && j==0){
			dp[i][j]=0;
			continue;
		}
		dp[i][j] = 0;
		if(i > 0) {
			if(dp[i-1][j] == n) dp[i][j] = n;
			else {
				amax(dp[i][j], prochain[dp[i-1][j]]);
			}
		}
		if(j > 0) {
			if(dp[i][j-1] == n) dp[i][j] = n;
			else {
				amax(dp[i][j], prochain2[dp[i][j-1]]);
			}
		}
	}
	return dp[p][q] >= n;
}

void solve(int test_case) {
	cin >> n >> p >> q;
	a.resize(n);
	FOR(i, n) cin >> a[i];
	sort(all(a));
	if(p + q >= n) {
		cout << 1 << endl;
		return;
	}
	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 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 640 KB Output is correct
12 Correct 5 ms 640 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 4 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 6 ms 512 KB Output is correct
8 Correct 17 ms 1664 KB Output is correct
9 Correct 18 ms 4224 KB Output is correct
10 Correct 25 ms 9344 KB Output is correct
11 Correct 21 ms 1792 KB Output is correct
12 Correct 98 ms 12024 KB Output is correct
13 Correct 5 ms 512 KB Output is correct
14 Correct 5 ms 512 KB Output is correct
15 Correct 5 ms 512 KB Output is correct