Pagini recente » Cod sursa (job #1809075) | Cod sursa (job #1942848) | Cod sursa (job #1987612) | Cod sursa (job #1649190) | Cod sursa (job #2933456)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
deque<int> q;
int n, l, u, a[30001], b[30001];
float ls, ld, mij, sum, c[30001], minim[30001];
int solve(float k)
{
c[0] = 0;
deque<int> d;
for(int i = 1; i <= n; ++ i)
c[i] = c[i - 1] + (a[i] - k * b[i]);
d.push_back(0);
minim[0] = 0;
for(int i = 1; i <= n; ++ i)
{
while(!d.empty() && c[i] <= c[d.back()])
d.pop_back();
d.push_back(i);
if(i - d.front() == u - l + 1)
d.pop_front();
minim[i] = c[d.front()];
}
for(int i = l; i <= n; ++ i)
{
if(c[i] - minim[i - l] >= 0)
return 1;
}
return 0;
}
int main()
{
fin >> n >> l >> u;
for(int i = 1; i <= n; ++ i)
{
fin >> a[i];
}
for(int i = 1; i <= n; ++ i)
{
fin >> b[i];
}
ls = 0.001;
ld = 1000;
for(int i = 1; i <= 40; ++ i)
{
mij = (ls + ld) / 2;
if(solve(mij) == 1)
ls = mij;
else
ld = mij;
}
fout << fixed << setprecision(3) << ls;
return 0;
}