#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i<= b; ++i)
#define FORD(i, a, b) for (int i = a; i>=b; --i)
#define REP(i, a) for (int i = 0; i<a; ++i)
#define DEBUG(x) { cerr << #x << " = " << x << endl; }
#define Arr(A, l, r) { cerr << #A << " = "; FOR(_, l, r) cerr << A[_] << ' '; cerr << endl; }
#define N 2020
#define pp pair<int, int>
#define next __next
#define prev __prev
#define __builtin_popcount __builtin_popcountll
#define bit(S, i) (((S) >> i) & 1)
#define IO cin.tie(NULL);cout.tie(NULL);
#define taskname "Test"
using namespace std;
int n, p, q, dp[N][N], a[N];
//dp[i][j] : Minimun the large camera used when fill from 1..i, used j small camera
bool ok(int w) {
FOR(i, 0, n) FOR(j, 0, p) dp[i][j] = 1e9;
dp[0][0] = 0;
FOR(i, 1, n) {
int psmall = upper_bound(a + 1, a + n + 1, a[i] - w + 1) - a - 1;
int plarge = upper_bound(a + 1, a + n + 1, a[i] - w - w + 1) - a - 1;
dp[i][0] = dp[plarge][0] + 1;
FOR(j, 1, p) {
dp[i][j] = min(dp[psmall][j - 1], dp[plarge][j] + 1);
}
}
FOR(j, 0, p) if(dp[n][j] <= q) return true;
return false;
}
int main() {
IO; ios :: sync_with_stdio(false);
cin >> n >> p >> q;
p = min(p, n);
FOR(i, 1, n) cin >> a[i];
sort(a + 1, a + n + 1);
int l = 0, r = 1e9, cur = -1;
while (l <= r) {
int m = (l + r) >> 1;
if (ok(m)) {
cur = m;
r = m - 1;
} else l = m + 1;
}
cout << cur;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
18120 KB |
Output is correct |
| 2 |
Correct |
0 ms |
18120 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
18120 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
18120 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
18120 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
