Pagini recente » Cod sursa (job #1697676) | Cod sursa (job #867561) | Cod sursa (job #3287987) | Cod sursa (job #2205503) | Cod sursa (job #3315376)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
const int Nmax = 3e4 + 5;
int n, U, L;
float c[Nmax], t[Nmax], prefix[Nmax];
bool verif(float k)
{
for(int i = 1; i <= n; ++i)
prefix[i] = prefix[i - 1] + c[i] - k * t[i];
deque<int> dq;
float 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];
float st = 1, dr = n, best = 0;
for(int i = 1; i <= 100; ++i)
{
float mij = (st + dr) / 2;
if(verif(mij)){
best = mij;
st = mij + 1;
}
else
dr = mij - 1;
}
fout << fixed << setprecision(2) << best;
return 0;
}