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 <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});
}
int dp[MAX_N+1][MAX_N+1];
bool chk(ll x){
for(int i=0; i<=N; i++){
for(int j=0; j<=min(N, P); j++){
dp[i][j] = INFLL;
}
}
//cout<<x<<endl;
int r1=0, r2=0;
dp[0][0] = 0;
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++;
}
for(int j=min(i, P); j>=0; j--){
if(dp[i][j]==INFLL) continue;
if(i==N){
if(j<=P && dp[i][j]<=Q) return true;
}else{
if(dp[i][j]>Q) continue;
dp[r1][j+1] = min(dp[r1][j+1], dp[i][j]);
dp[r2][j] = min(dp[r2][j], dp[i][j]+1);
}
}
}
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 (stderr)
watching.cpp: In function 'bool chk(ll)':
watching.cpp:37: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:40: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:58: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:61:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
ll x; scanf("%lld", &x);
~~~~~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |