이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//todo
//ajihuwi
#define NDEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//#define dbg(TXTMSG) cerr << "\n" << TXTMSG
//#define dbgv(VARN) cerr << "\n" << #VARN << " = "<<VARN << ", line: " << __LINE__ << "\n"
ll N, P/*small*/, Q/*big*/;
vector<ll> A;
vector<ll> covered_prefix_2w;
vector<ll> covered_prefix_w;
//constexpr ll MAX_N = 2002;
//constexpr ll MAX_CAMERA = MAX_N;
vector<vector<ll>> dp;
bool is_cam_placement_possible(ll w) {
ll w2_before_indice = 0;
ll w_before_indice = 0;
for (ll i = 0; i < N; i++) {
while (A[w_before_indice] <= (A[i]-w)) {
w_before_indice++;
}
while (A[w2_before_indice] <= (A[i]-2*w)) {
w2_before_indice++;
}
covered_prefix_w[i]=w_before_indice;
covered_prefix_2w[i]=w2_before_indice;
}
for (ll sectiontill = 1; sectiontill <= N; sectiontill++)
{
dp[sectiontill][0] = dp[covered_prefix_w[sectiontill-1]][0]+1;
for (ll numbigcam = 1; numbigcam <= Q; numbigcam++)
{
dp[sectiontill][numbigcam] = min({
dp[covered_prefix_2w[sectiontill-1]][numbigcam-1],
dp[covered_prefix_w[sectiontill-1]][numbigcam]+1
});
}
if (dp[sectiontill][Q] > P) {
return false;
}
if (dp[sectiontill][Q]+N-sectiontill <= P) {
return true;
}
}
return (dp[N][Q] <= P);
}
int main() {
cin.tie(nullptr);
cin.sync_with_stdio(false);
cin >> N >> P >> Q;
A = vector<ll>(N);
covered_prefix_2w = vector<ll>(N);
covered_prefix_w = vector<ll>(N);
for (ll i = 0; i < N; i++)
{
cin >> A[i];
}
sort(A.begin(),A.end());
if (N==0) {
cout << "0";
return EXIT_SUCCESS;
}
if (N <= (P+Q)) {
cout << "1";
return EXIT_SUCCESS;
}
dp.assign(N+1,vector<ll>(Q+1,0));
ll max_possible_w = 1ll + (*A.crbegin())/(P+Q);
ll min_possible_w = 1ll;
while (max_possible_w > min_possible_w) {
ll mid = (min_possible_w+min_possible_w)/2;
if (is_cam_placement_possible(mid)) {
max_possible_w = mid;
}
else {
min_possible_w = mid+1;
}
}
cout << min_possible_w;
}
/*
13 3 2
33
66
99
10
83
68
19
83
93
53
15
66
75*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |