oj.uz

Submission #507633

# Submission time Handle Problem Language Result Execution time Memory
507633 2022-01-12T21:10:15 Z thiago_bastos Watching (JOI13_watching) C++17
100 / 100
 582 ms 16920 KB 
#include "bits/stdc++.h"

using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using i32 = int;
using u32 = unsigned;
using i16 = short;
using u16 = unsigned short;
using ld = long double;
using ii = pair<int, int>;

const int inf = 1e9, N = 2e3 + 100;

int n, p, q;
array<int, N> dp[2];

vector<int> a;

bool f(int w) {
	for(int i = 0; i <= n; ++i) dp[0][i] = -inf;
	dp[0][0] = 0;
	for(int i = 1; i <= p + q; ++i) {
		int hi[2] = {0};
		for(int i = 0; i <= n; ++i) dp[1][i] = -inf;
		for(int k = 0; k < n; ++k) {
			while(hi[0] < n && a[hi[0]] - a[k] < w) ++hi[0];
			while(hi[1] < n && a[hi[1]] - a[k] < 2 * w) ++hi[1];
			dp[1][hi[0]] = max(dp[1][hi[0]], dp[0][k] + 1);
			dp[1][hi[1]] = max(dp[1][hi[1]], dp[0][k]);
		}
		swap(dp[0], dp[1]);
		if(dp[0][n] >= p || i - dp[0][n] <= q) return true;
	}
	return false;
}

void solve() {

	cin >> n >> p >> q;

	a.resize(n);

	for(int i = 0; i < n; ++i) cin >> a[i];

	if(p + q >= n) {
		cout << "1\n";
		return;
	}

	sort(a.begin(), a.end());

	vector<int> d;

	for(int i = 0; i < n; ++i) {
		for(int j = i + 1; j < n; ++j) {
			d.push_back(a[j] - a[i] + 1);
			d.push_back((a[j] - a[i] + 2) / 2);
		}
	}

	sort(d.begin(), d.end());
	d.resize(unique(d.begin(), d.end()) - d.begin());

	int lo = 0, hi = (int)d.size() - 1;

	while(lo < hi) {
		int mid = (lo + hi) / 2;
		if(f(d[mid])) hi = mid;
		else lo = mid + 1;	
	}

	cout << d[hi] << '\n';
}		

int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) solve();
	return 0;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 3 ms 332 KB Output is correct
11 Correct 2 ms 308 KB Output is correct
12 Correct 3 ms 332 KB Output is correct
13 Correct 1 ms 312 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 2 ms 332 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 16896 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 299 ms 16864 KB Output is correct
8 Correct 506 ms 16820 KB Output is correct
9 Correct 539 ms 16820 KB Output is correct
10 Correct 574 ms 16820 KB Output is correct
11 Correct 553 ms 16828 KB Output is correct
12 Correct 582 ms 16828 KB Output is correct
13 Correct 166 ms 16828 KB Output is correct
14 Correct 188 ms 16828 KB Output is correct
15 Correct 239 ms 16920 KB Output is correct