oj.uz

Submission #304228

# Submission time Handle Problem Language Result Execution time Memory
304228 2020-09-21T04:49:32 Z shrek12357 Watching (JOI13_watching) C++14
100 / 100
 174 ms 16128 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <fstream>
#include <queue>
using namespace std;

const int MAXN = 2005;

int n, a, b;
vector<int> nums;	
int dp[MAXN][MAXN];

int idx(int val) {
	int ans = -1;
	int lo = 0, hi = n - 1;
	while (lo <= hi) {
		int mid = (lo + hi) / 2;
		if (nums[mid] < val) {
			lo = mid + 1;
			ans = max(ans, mid);
		}
		else {
			hi = mid - 1;
		}
	}
	return ans;
}

bool check(int mid) {
	int calc1[MAXN], calc2[MAXN];
	for (int i = 0; i < n; i++) {
		calc1[i] = idx(nums[i] - mid + 1);
		calc2[i] = idx(nums[i] - 2 * mid + 1);
	}
	for (int i = 0; i < n; i++) {
		int cur = idx(nums[i] - 2 * mid + 1);
		if (cur == -1) {
			dp[i][0] = 1;
		}
		else {
			dp[i][0] = dp[cur][0] + 1;
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 1; j <= min(a, n); j++) {
			int val1 = calc1[i];
			int val2 = calc2[i];
			int c1 = INT_MAX, c2 = INT_MAX;
			if (val1 == -1) {
				c1 = 0;
			}
			else {
				c1 = dp[val1][j - 1];
			}
			if (val2 == -1) {
				c2 = 1;
			}
			else {
				c2 = dp[val2][j] + 1;
			}
			dp[i][j] = min(c1, c2);
		}
	}
	for (int i = 0; i <= min(a, n); i++) {
		if (dp[n - 1][i] <= b) {
			return true;
		}
	}
	return false;
}

int main() {
	cin >> n >> a >> b;
	for (int i = 0; i < n; i++) {
		int temp;
		cin >> temp;
		nums.push_back(temp);
	}
	sort(nums.begin(), nums.end());
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			dp[i][j] = (int)1e9;
		}
	}
	int lo = 1;
	int hi = (int)1e9;
	int ans = INT_MAX;
	while (lo <= hi) {
		int mid = (lo + hi) / 2;
		if (check(mid)) {
			ans = min(ans, mid);
			hi = mid - 1;
		}
		else {
			lo = mid + 1;
		}
	}
	cout << ans << endl;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 768 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 768 KB Output is correct
5 Correct 2 ms 768 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Correct 1 ms 768 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 1 ms 768 KB Output is correct
10 Correct 1 ms 768 KB Output is correct
11 Correct 1 ms 768 KB Output is correct
12 Correct 1 ms 768 KB Output is correct
13 Correct 1 ms 768 KB Output is correct
14 Correct 1 ms 768 KB Output is correct
15 Correct 1 ms 768 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 16000 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 142 ms 16084 KB Output is correct
4 Correct 166 ms 16128 KB Output is correct
5 Correct 28 ms 16000 KB Output is correct
6 Correct 170 ms 16108 KB Output is correct
7 Correct 21 ms 16000 KB Output is correct
8 Correct 33 ms 16000 KB Output is correct
9 Correct 90 ms 16104 KB Output is correct
10 Correct 174 ms 16104 KB Output is correct
11 Correct 30 ms 16000 KB Output is correct
12 Correct 105 ms 16000 KB Output is correct
13 Correct 24 ms 16000 KB Output is correct
14 Correct 25 ms 16000 KB Output is correct
15 Correct 25 ms 16000 KB Output is correct