#include<bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define FOR(i,n) for(i=0;i<(n);i++)
#define FORe(i,n) for(i=1;i<=(n);i++)
#define FORr(i,a,b) for(i=(a);i<(b);i++)
#define ii pair<ll,ll>
#define vi vector<ll>
#define vii vector<ii>
#define ff first
#define ss second
#define cd complex<double>
#define vcd vector<cd>
#define ldd long double
#define all(x) (x).begin(),(x).end()
using namespace std;
const short int __PRECISION = 10;
const ll MOD = 1e9+7;
const ll INF = 1e17 + 1101;
const ll LOGN = 17;
const ll MAXN = 2e5+5;
const ll ROOTN = 320;
const ldd PI = acos(-1);
const ldd EPS = 1e-7;
ll N,P,Q,A[2005];
bool is_doable(ll w)
{
//cout<<"---------------\nChecking is_doable("<<w<<")\n";
ll i,j,dp[P+1][Q+1],small[N],big[N],a,b;
FOR(i,P+1)
FOR(j,Q+1)
dp[i][j] = 0;// -1;
FOR(i,N)
small[i] = big[i] = i;
queue<ii> Qs,Qb;
Qb.push(mp(A[0],0));
Qs.push(mp(A[0],0));
small[0] = big[0] = 0;
FORe(i,N-1)
{
while(!Qs.empty() and A[i] - (Qs.front()).ff >= w)
Qs.pop();
Qs.push(mp(A[i],i));
while(!Qb.empty() and A[i] - (Qb.front()).ff >= 2*w)
Qb.pop();
Qb.push(mp(A[i],i));
small[(Qs.front()).ss] = i;
big[(Qb.front()).ss] = i;
}
while(!Qs.empty())
{
small[(Qs.front()).ss] = N-1;
Qs.pop();
}
while(!Qb.empty())
{
big[(Qb.front()).ss] = N-1;
Qb.pop();
}
dp[1][0] = small[0];
dp[0][1] = big[0];
//FOR(i,N)
// cout<<"small["<<i<<"] = "<<small[i]<<", and big["<<i<<"] = "<<big[i]<<endl;
FOR(i,P+1)
FOR(j,Q+1)
{
if((j == 0 and i == 0))
continue;
if (dp[i][j] == -1) {cout<<"DANGER\n";cin>>a;}
if (dp[i][j] >= N-1)
{
//cout<<w<<" is doable\n";
return true;
}
a = small[dp[i][j]+1];
b = big[dp[i][j]+1];
if (i < P)
dp[i+1][j] = max(dp[i+1][j],a);
if (j < Q)
dp[i][j+1] = max(dp[i][j+1],b);
}
//cout<<w<<" isn't doable\n";
return false;
}
inline void bs()
{
ll mid,lo = 1,hi = A[N-1] - A[0] + 1;
long double p;
while(lo < hi - 1)
{
mid = (lo + hi)/2;
if(is_doable(mid))
hi = mid;
else
lo = mid;
}
p = hi*1.00;
p = p/2.00;
cout<<fixed<<setprecision(3)<<p<<endl;
}
int main()
{
/*
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
*/
ll i,j;
cin>>N>>P>>Q;
set<ll> x;
FOR(i,N)
{
cin>>j;
x.insert(j);
}
i = 0;
N = x.size();
for(ll a : x)
A[i++] = 2*a;
if (P+Q >= N)
{
cout<<1;
exit(0);
}
if (is_doable(1))
{
cout<<1;
exit(0);
}
bs();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
