Pagini recente » Cod sursa (job #2085206) | Cod sursa (job #2406974) | Profil mgpaduraru | Cod sursa (job #78892) | Cod sursa (job #1687415)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
const int MAXN = 30007;
int N , L , U , A[MAXN] , B[MAXN] ;
double v[MAXN];
void citire()
{
fin >> N>> L >> U;
for(int i = 1 ; i <= N ; ++i)
fin >> A[i];
for(int i = 1; i<=N; ++i)
fin >> B[i];
}
double Get()
{
double s = 0;
for(int i = 1 ; i<=N; ++i)
s += 1.0 * A[i] / (1.0 * B[i]);
return s;
}
void trans(double mij)
{
for(int i = 1; i<=N; ++i) v[i] = A[i];
for(int i=1;i<=N; ++i)
v[i] -= mij * B[i];
for(int i = 2 ; i <=N; ++i)
v[i] += v[i-1];
}
void sterg(deque<pair<int, double>>&D, int i, int j)
{
while(!D.empty() && (D.front().first < i || D.front().first > j)) D.pop_front();
}
bool grt(double a, double b)
{
return a - b > 0.01;
}
bool ok(double mij)
{
trans(mij);
deque < pair<int, double>> D;
for(int i = 1 ; i<=N; ++i)
{
while(!D.empty() && D.back().second >= v[i - 1]) D.pop_back();
sterg(D, i - U + 1, i - L + 1);
D.push_back(make_pair(i, v[i - 1]));
sterg(D, i - U + 1, i - L + 1);
if(!D.empty() && grt(v[i], D.front().second ))return 1;
}
return 0;
}
void solve()
{
double st = 0 , dr = Get(), res = 0;
for(int i = 0; i <= 30; ++i)
{
double m = (st+dr) / 2.0;
if(ok(m) == 0) res = m , dr=m-1;
else st=m+1;
}
fout<<fixed<<setprecision(4)<<res<<'\n';
}
int main()
{
citire();
solve();
}