Pagini recente » Cod sursa (job #3250308) | Cod sursa (job #1486802) | Cod sursa (job #891820) | Cod sursa (job #1476201) | Cod sursa (job #3315380)
#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)
{
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])
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 = 1, dr = n, best = 0;
for(int i = 1; i <= 100; ++i)
{
double mij = (st + dr) / 2;
if(verif(mij)){
best = mij;
st = mij + 1;
}
else
dr = mij - 1;
}
fout << fixed << setprecision(2) << best;
return 0;
}