oj.uz

Submission #85555

# Submission time Handle Problem Language Result Execution time Memory
85555 2018-11-20T22:38:54 Z KCSC Watching (JOI13_watching) C++14
0 / 100
 399 ms 14200 KB 
#include <bits/stdc++.h>
using namespace std;

const int DIM = 2005;

int pos[DIM], pos1[DIM], pos2[DIM], dp[DIM][DIM];

int main(void) {
/*
#ifdef HOME
	freopen("watching.in", "r", stdin);
	freopen("watching.out", "w", stdout); 
#endif
*/
	int n, p, q; cin >> n >> p >> q;
	for (int i = 1; i <= n; ++i) {
		cin >> pos[i]; }
	int le = 1, ri = 1000000000;
	while (le <= ri) {
		int md = (le + ri) / 2;
		for (int i = 1; i <= n; ++i) {
			pos1[i] = pos2[i] = 0;
			for (int j = 1; j < i; ++j) {
				if (pos[i] - md >= pos[j]) {
					pos1[i] = j; }
				if (pos[i] - md * 2 >= pos[j]) {
					pos2[i] = j; } }
			for (int j = 0; j <= i; ++j) {
				dp[i][j] = dp[pos2[i]][j] + 1;
				if (j > 0) {
					dp[i][j] = min(dp[i][j], dp[pos1[i]][j - 1]); } } } 	
		int ans = 1000000000;
		for (int i = 0; i <= min(p, q); ++i) {
			ans = min(ans, dp[n][i]); }
		if (ans <= q) {
			ri = md - 1; }
		else {
			le = md + 1; } }
	cout << le;
	return 0; }

Subtask #1
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 399 ms 14200 KB Output isn't correct
2 Halted 0 ms 0 KB -