oj.uz

Submission #464325

# Submission time Handle Problem Language Result Execution time Memory
464325 2021-08-13T00:35:24 Z Hamed5001 Watching (JOI13_watching) C++14
0 / 100
 71 ms 16144 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int mxN = 2e3+10, OO = 0x3f3f3f3f;
ll A[mxN], N, P, Q;
int dp[mxN][mxN];

bool ok(ll mid) {
	memset(dp, OO, sizeof dp);
	dp[0][0] = 0;

	for (int i = 0; i < N; i++) {
		int nxt_p = lower_bound(A, A+N, A[i] + mid) - A;
		int nxt_q = lower_bound(A, A+N, A[i] + 2 * mid) - A;
		for (int np = 0; np <= P; np++) {
			dp[nxt_p][np+1] = min(dp[nxt_p][np+1], dp[i][np]);
			dp[nxt_q][np] = min(dp[nxt_p][np], dp[i][np]+1);
		}
	}

	for (int i = 0; i <= P; i++) if (dp[N][i] <= Q) return 1;
	return 0;
}

void solve() {
	cin >> N >> P >> Q;
	P = min(P, N);
	Q = min(Q, N);
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}

	ll l = 1, r = 1e10, mid;
	while(l < r) {
		mid = (l+r) >> 1;
		if (ok(mid)) r = mid;
		else l = mid+1;
	}
	cout << r << endl;
}

int main() {
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	solve();
}

Subtask #1
0 / 50.0

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

Subtask #2
0 / 50.0

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