#include <bits/stdc++.h>
#define FOR(i,x,n) for(int i=x; i<n; i++)
#define F0R(i,n) FOR(i,0,n)
#define ROF(i,x,n) for(int i=n-1; i>=x; i--)
#define R0F(i,n) ROF(i,0,n)
#define WTF cout << "WTF" << endl
#define IOS ios::sync_with_stdio(false); cin.tie(0)
#define F first
#define S second
#define pb push_back
#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<PII> VPII;
typedef vector<PLL> VPLL;
const int N = 2000 + 7;
const int ALPHA = 27;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const int LOG = 22;
int n, s, b;
int ns[N], dp[N][N];
// dp[i][j] = until i'th place, having j small cameras.
inline bool check(int w) {
FOR(i, 1, n + 1) F0R(j, n + 1) {
int pl = lower_bound(ns + 1, ns + n + 1, ns[i] - 2 * w) - ns;
//cout << "when updating " << i << ' ' << j << " using " << pl - 1 << ' ' << j << endl;
dp[i][j] = dp[pl - 1][j] + 1;
if (j) {
pl = lower_bound(ns + 1, ns + n + 1, ns[i] - w) - ns;
dp[i][j] = min(dp[i][j], dp[pl - 1][j - 1]);
//cout << "but when updating " << i << ' ' << j << " using " << pl - 1 << ' ' << j - 1 << endl;
}
}
//cout << "check(" << w << ") = " << dp[n][min(n, s)] << endl;
//FOR(i, 1, n + 1) F0R(j, n + 1) cout << dp[i][j] << " \n"[j == n];
return (dp[n][min(n, s)] <= b);
}
int main() {
IOS;
cin >> n >> s >> b;
FOR(i, 1, n + 1) cin >> ns[i];
ns[0] = -INF;
sort(ns + 1, ns + n + 1);
int l = 1, r = INF;
//cout << check(4) << endl;
while(l < r) {
int mid = (l + r) >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
cout << l + 1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
712 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1074 ms |
15984 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
