Pagini recente » Cod sursa (job #3321337) | Cod sursa (job #942737) | Cod sursa (job #3311619) | Cod sursa (job #230965) | Cod sursa (job #3315382)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
const int Nmax = 3e4 + 5;
int n, L, U;
double c[Nmax], t[Nmax], prefix[Nmax];
bool verif(double k)
{
prefix[0] = 0;
for (int i = 1; i <= n; ++i)
prefix[i] = prefix[i - 1] + c[i] - k * t[i];
deque<int> dq;
double rez = 0;
for (int i = L; i <= n; ++i)
{
while (!dq.empty() && prefix[dq.back()] >= prefix[i - L + 1])
dq.pop_back();
dq.push_back(i - L);
if (!dq.empty())
rez = max(rez, prefix[i] - prefix[dq.front()]);
if (!dq.empty() && dq.front() < i - U)
dq.pop_front();
}
return (rez > 0);
}
int main()
{
fin >> n >> L >> U;
for (int i = 1; i <= n; ++i) fin >> c[i];
for (int i = 1; i <= n; ++i) fin >> t[i];
double st = 0, dr = n, best = 0;
for(int it = 0; it < 60; ++it)
{
double mij = (st + dr) / 2;
if (verif(mij)){
best = mij;
st = mij;
}
else
dr = mij;
}
fout << fixed << setprecision(2) << st;
return 0;
}