#include <bits/stdc++.h>
using namespace std;
long long n, p, q;
long long a[200005];
/*
bool check(long long w){
long long smallCam = p;
long long bigCam = q;
for(long long i = 0; i < n; ++i){
long long ind1 = upper_bound(a, a + n, a[i] + w - 1) - a;
long long ind2 = upper_bound(a, a + n, a[i] + 2 * w - 1) - a;
if(ind2 > ind1){
if(bigCam){
bigCam--;
i = ind2 - 1;
continue;
}
}
if(smallCam){
smallCam--;
i = ind1 - 1;
}else if(bigCam){
bigCam--;
i = ind2 - 1;
}else{
return false;
}
}
return true;
}
*/
bool cmp(pair<long long, long long> x, pair<long long, long long> y){
return (x.second - x.first + 1) > (y.second - y.first + 1); ///sort, by real dist, or index dist?
}
long long st[8005];
long long lazy[8005];
void updNode(long long val, long long id, long long l, long long r){
lazy[id] += val;
st[id] += (r - l + 1) * val;
}
void shift(long long id, long long l, long long r){
long long mid = (l + r) / 2;
updNode(lazy[id], id * 2 + 1, l, mid);
updNode(lazy[id], id * 2 + 2, mid + 1, r);
lazy[id] = 0;
}
void update(long long x, long long y, long long val, long long id, long long l, long long r){
if(x > r || y < l){
return;
}
if(x <= l && r <= y){
updNode(val, id, l, r);
return;
}
shift(id, l, r);
long long mid = (l + r) / 2;
update(x, y, val, id * 2 + 1, l, mid);
update(x, y, val, id * 2 + 2, mid + 1, r);
st[id] = st[id * 2 + 1] + st[id * 2 + 2];
}
long long gSum(long long x, long long y, long long id, long long l, long long r){
if(x > r || y < l){
return 0;
}
if(x <= l && r <= y){
return st[id];
}
shift(id, l, r);
long long mid = (l + r) / 2;
long long v1 = gSum(x, y, id * 2 + 1, l, mid);
long long v2 = gSum(x, y, id * 2 + 2, mid + 1, r);
return v1 + v2;
}
void build(long long id, long long l, long long r){
if(l == r){
st[id] = 0;
lazy[id] = 0;
return;
}
long long mid = (l + r) / 2;
build(id * 2 + 1, l, mid);
build(id * 2 + 2, mid + 1, r);
st[id] = 0;
lazy[id] = 0;
}
bool check(long long w){
build(0, 0, n - 1);
vector<pair<long long, long long>> prs;
for(long long i = 0; i < n; ++i){
for(long long j = i; j < n; ++j){
prs.push_back({i, j});
}
}
long long numBig = q;
long long numSmall = p;
sort(prs.begin(), prs.end(), cmp);
for(long long i = 0; i < (long long)prs.size(); ++i){
long long x = prs[i].first;
long long y = prs[i].second;
long long val = gSum(x, y, 0, 0, n - 1);
if(val){
continue;
}
if(a[y] - a[x] + 1 <= 2 * w){
if(numBig){
numBig--;
update(x, y, 1, 0, 0, n - 1);
}else if(numSmall && a[y] - a[x] + 1 <= w){
numSmall--;
update(x, y, 1, 0, 0, n - 1);
}
}
}
long long ttSum = gSum(0, n - 1, 0, 0, n - 1);
if(ttSum >= n){
return true;
}
return false;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> p >> q;
for(long long i = 0; i < n; ++i){
cin >> a[i];
}
sort(a, a + n);
long long l = 0;
long long r = 1000000000;
long long lc = -1;
while(l <= r){
long long mid = (l + r) / 2;
bool ch = check(mid);
if(ch){
r = mid - 1;
lc = mid;
}else{
l = mid + 1;
}
}
cout << lc << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1078 ms |
49664 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
