#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAX_N = 2002;
const ll INFLL = 10000;
int N, P, Q;
vector<ll> v;
list<pii> dq[2][MAX_N+1];
void add(int idx, int x, int y, int z){
while(!dq[idx][x].empty() && dq[idx][x].back().first>=z){
dq[idx][x].pop_back();
}
dq[idx][x].push_back({z, y});
}
bool chk(ll x){
for(int i=0; i<=N; i++){
while(!dq[0][i].empty()) dq[0][i].pop_back();
while(!dq[1][i].empty()) dq[1][i].pop_back();
}
dq[0][0].pb({0, 0});
//cout<<x<<endl;
int r1=0, r2=0, k;
for(int i=0; i<=N; i++){
while(r1<v.size()-1 && v[r1+1]<=v[i+1]+x-1LL){
r1++;
}
while(r2<v.size()-1 && v[r2+1]<=v[i+1]+2LL*x-1LL){
r2++;
}
bool tf = true;
for(int j=min(i, P); j>=0; j--){
while(!dq[0][j].empty() && dq[0][j].front().second<i) dq[0][j].pop_front();
while(!dq[1][j].empty() && dq[1][j].front().second<i) dq[1][j].pop_front();
if(dq[0][j].empty()){
if(!dq[1][j].empty()) k = dq[1][j].front().first;
else continue;
}else{
if(dq[1][j].empty()) k = dq[0][j].front().first;
else{
k = min(dq[0][j].front().first, dq[1][j].front().first);
}
}
tf = false;
if(i==N){
if(j<=P && k<=Q) return true;
}else{
if(k>Q) continue;
add(0, j+1, r1, k);
add(1, j, r2, k+1);
}
}
if(tf) break;
}
return false;
}
int main(){
scanf("%d%d%d", &N, &P, &Q);
v.pb(0);
for(int i=1; i<=N; i++){
ll x; scanf("%lld", &x);
v.pb(x);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
sort(v.begin(), v.end());
N = v.size()-1;
ll s = 1LL, e = 1000000000LL, m;
while(s<e){
m = (s+e)/2LL;
if(chk(m)){
e = m;
}else{
s = m+1;
}
}
printf("%lld", s);
}
Compilation message
watching.cpp: In function 'bool chk(ll)':
watching.cpp:34:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(r1<v.size()-1 && v[r1+1]<=v[i+1]+x-1LL){
~~^~~~~~~~~~~
watching.cpp:37:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(r2<v.size()-1 && v[r2+1]<=v[i+1]+2LL*x-1LL){
~~^~~~~~~~~~~
watching.cpp: In function 'int main()':
watching.cpp:68:7: 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:71:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
ll x; scanf("%lld", &x);
~~~~~^~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
9 ms |
376 KB |
Output is correct |
5 |
Correct |
5 ms |
376 KB |
Output is correct |
6 |
Correct |
15 ms |
376 KB |
Output is correct |
7 |
Correct |
3 ms |
376 KB |
Output is correct |
8 |
Correct |
3 ms |
376 KB |
Output is correct |
9 |
Correct |
5 ms |
380 KB |
Output is correct |
10 |
Correct |
6 ms |
376 KB |
Output is correct |
11 |
Correct |
9 ms |
376 KB |
Output is correct |
12 |
Correct |
10 ms |
376 KB |
Output is correct |
13 |
Correct |
4 ms |
376 KB |
Output is correct |
14 |
Correct |
4 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
380 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
504 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Execution timed out |
1074 ms |
556 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |