//todo
//ajihuwi
//#define _GLIBCXX_DEBUG
#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 = 2004;
constexpr ll MAX_CAMERA = MAX_N;
vector<array<ll,MAX_CAMERA>> 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;
}
array<ll,MAX_CAMERA> filledarr;
filledarr.fill(-1);
dp.assign(N+1,filledarr);
dp[0].fill(0);
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
});
}
}
return (dp[N][Q] <= P);
}
int main() {
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());
ll max_possible_w = 1000000002ll;
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;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1068 ms |
1876 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1035 ms |
31700 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |