Pagini recente » Cod sursa (job #1783868) | Cod sursa (job #356546) | Cod sursa (job #20876) | Cod sursa (job #1279784) | Cod sursa (job #2215144)
#include <bits/stdc++.h>
using namespace std;
ifstream in("secv3.in");
ofstream out("secv3.out");
const int NMAX = 30000;
const int VMAX = 1000;
double vals[NMAX+2], a[NMAX+2], b[NMAX+2];
int N, L, H;
bool OK(double M)
{
for( int i = 1; i <= N; ++i )
vals[i] = vals[i - 1] + a[i] - M * b[i];
deque<int> dq;
for( int i = 1, st = i - H, dr = i - L; i <= N; ++i, ++st, ++dr ) {
if( dr >= 0 ) {
while( !dq.empty() && vals[ dq.back() ] >= vals[dr] )
dq.pop_back();
dq.push_back(dr);
}
if( st >= 0 ) {
while( !dq.empty() && dq.front() < st )
dq.pop_front();
}
if( !dq.empty() && vals[i] >= vals[ dq.front() ] )
return 1;
}
return 0;
}
int main()
{
in >> N >> L >> H;
for( int i = 1; i <= N; ++i ) in >> a[i];
for( int i = 1; i <= N; ++i ) in >> b[i];
double st = 1e-3, dr = VMAX * NMAX, best = 0;
for( int step = 0; step < 60; ++step ) {
double mid = (st + dr) / 2.0;
if( OK(mid) ) {
best = mid;
st = mid;
}
else
dr = mid;
}
out << setprecision(2) << fixed << best << '\n';
return 0;
}