This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int N = 2202;
int n, p, q;
int a[N];
int f[N][N];
struct SegmentTreeMin{
int it[N * 4];
#define mid ((l + r) >> 1)
void build(int x, int l, int r){
it[x] = 1e9;
if(l == r) {
return;
}
build(x + x, l, mid);
build(x + x + 1, mid + 1, r);
}
void modify(int x, int l, int r, int pos, int val){
if(l > pos || r < pos) return;
it[x] = min(it[x], val);
if(l == r) return;
modify(x + x, l, mid, pos, val);
modify(x + x + 1, mid + 1, r, pos, val);
}
int query(int x, int l, int r, int u, int v){
if(l > v || r < u) return 1e9;
if(l >= u && r <= v) return it[x];
return min(query(x + x, l, mid, u, v), query(x + x + 1, mid + 1, r, u, v));
}
}g[N];
int main(){
if(fopen("1.inp", "r")){
freopen("1.inp", "r", stdin);
}
scanf("%d%d%d", &n, &p, &q);
for(int i = 1; i <= n; ++i){
scanf("%d", a + i);
}
p = min(p, n);
q = min(q, n);
sort(a + 1, a + n + 1);
int low = 1, high = 1e9, ans = 1e9;
while(low <= high){
int w = (low + high) >> 1;
memset(f, 60, sizeof f);
f[0][0] = 0;
for(int i = 0; i <= p; ++i){
g[i].build(1, 0, n);
}
g[0].modify(1, 0, n, 0, 0);
bool ok = false, debug = false;
for(int i = 1; i <= n; ++i){
for(int j = 0; j <= min(i, p); ++j){
if(j > 0){
int pos = lower_bound(a + 1, a + n + 1, a[i] - w + 1) - a;
f[i][j] = g[j - 1].query(1, 0, n, pos - 1, i);
}
int pos = lower_bound(a + 1, a + n + 1, a[i] - w - w + 1) - a;
f[i][j] = min(f[i][j], g[j].query(1, 0, n, pos - 1, i) + 1);
if(i == n && f[i][j] <= q){
ok = true;
}
g[j].modify(1, 0, n, i, f[i][j]);
}
}
if(ok == false){
low = w + 1;
}
else{
ans = w;
high = w - 1;
}
}
cout << ans;
return 0;
}
Compilation message (stderr)
watching.cpp: In function 'int main()':
watching.cpp:71:20: warning: unused variable 'debug' [-Wunused-variable]
bool ok = false, debug = false;
^
watching.cpp:42:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("1.inp", "r", stdin);
^
watching.cpp:45:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &n, &p, &q);
^
watching.cpp:48:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", a + i);
^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |