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 <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <cstring>
int x, p, q;
std::vector<int> arr;
std::vector<int> next[2];
std::pair<int,int> dp[2001][500];
std::pair<int,int> solve(int pos, int k, int lambda) {
if (pos==x) {
return {0, 0};
}
if (dp[pos][k].second!=-1) {
return dp[pos][k];
}
std::pair<int,int> ret(-0x3f3f3f3f, -0x3f3f3f3f);
if (k<p) {
ret = std::max(ret, std::pair<int,int>(solve(next[0][pos], k+1, lambda).first + next[0][pos]-pos,
solve(next[0][pos], k+1, lambda).second));
}
ret = std::max(ret, std::pair<int,int>(solve(next[1][pos], k, lambda).first + next[1][pos]-pos - lambda,
solve(next[1][pos], k, lambda).second + 1));
return dp[pos][k] = ret;
}
bool can_solve(int cap) {
for (int i = 0; i < 2; i++) {
next[i].resize(x);
for (int l = x-1, r = x-1; l >= 0; l--) {
while (arr[r]-arr[l]+1>(i+1)*cap) {
--r;
}
next[i][l] = r+1;
}
}
const auto bs_lambda = [&]() {
int ret = -1;
int l = 0, r = 2000;
while (l<=r) {
int m = (l+r)>>1;
memset(dp,-1,sizeof(dp));
auto [max, cnt] = solve(0,0,m);
if (cnt<=q) {
ret = m;
l = m+1;
}
else {
r = m-1;
}
}
return ret;
};
int lambda = bs_lambda();
auto [max, cnt] = solve(0,0,lambda);
return (max + cnt*lambda == x);
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
std::cin >> x >> p >> q;
// we only need at most x cameras in total, out of which we'll greedily take as many big cameras as possible
if (p+q>x) {
q = std::min(q, x);
p = x-q;
}
for (int i = 0, tmp; i < x; i++) {
std::cin >> tmp;
arr.emplace_back(tmp);
}
std::sort(arr.begin(),arr.end());
const auto bs = [&]() {
int ret = 1000000001;
int l = 1, r = 1000000000;
while (l<=r) {
int m = (l+r)>>1;
if (can_solve(m)) {
ret = m;
r = m-1;
}
else {
l = m+1;
}
}
return ret;
};
std::cout << bs() << "\n";
//can_solve(bs(),1);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |