Pagini recente » Autentificare | Cod sursa (job #2174603) | Cod sursa (job #2323533) | Cod sursa (job #2087095) | Cod sursa (job #2922109)
#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];
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(c[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 + 1)
d.pop_front();
if(i >= l)
{
sum = 0;
sum = c[i] - c[d.front()];
if(sum >= 0)
return 0;
}
}
return 1;
}
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;
}