Pagini recente » Cod sursa (job #68558) | Cod sursa (job #719712) | Cod sursa (job #510983) | Cod sursa (job #245959) | Cod sursa (job #2431635)
#include <bits/stdc++.h>
using namespace std;
ifstream in("secv3.in");
ofstream out("secv3.out");
deque <int> d;
const int DIM = 1e5 + 7;
const int INF = 2e9;
int v[DIM];
int p[DIM];
double c[DIM];
int n, u, l;
bool check(double k)
{
d.clear();
for(int i = 1; i <= n; i++)
c[i] = v[i] * 1.0 - k * p[i] + c[i - 1];
double mx = c[l];
int dif = u - l;
for(int i = l; i <= n; i++)
{
while(!d.empty() && c[d.back()] >= c[i - l])
d.pop_back();
d.push_back(i - l);
while(!d.empty() && d.front() + u < i)
d.pop_front();
int x = 0;
if(!d.empty())
x = d.front();
mx = max(mx, c[i] - c[x]);
}
if(mx >= 0)
return true;
return false;
}
int main()
{
in >> n >> l >> u;
for(int i = 1; i <= n; i++)
in >> v[i];
for(int i = 1; i <= n; i++)
in >> p[i];
double st = 0;
double dr = 100000;
double ans = 0;
while(st + 0.001 <= dr)
{
double mid = (st + dr) / 2;
if(check(mid) == true)
{
st = mid;
ans = mid;
}
else
{
dr = mid;
}
}
out << fixed << setprecision(3) << ans;
}