Pagini recente » Cod sursa (job #1683758) | Cod sursa (job #1896638) | Cod sursa (job #1605555) | Cod sursa (job #2747165) | Cod sursa (job #2094327)
#include <bits/stdc++.h>
using namespace std;
ifstream in("secv3.in");
ofstream out("secv3.out");
const int NMAX = 30000, EPS = 0.001;
const double CMAX = 1000;
int n, l, u;
int c[NMAX + 2], t[NMAX + 2];
double ans;
double tmp[NMAX + 2];
bool check(double arg)
{
deque<int> dq;
for(int i = 1; i <= n; i++)
{
tmp[i] = c[i] - arg * t[i];
tmp[i] += tmp[i - 1];
}
for(int i = l; i <= n; i++)
{
while(!dq.empty() && dq.front() <= i - u)
dq.pop_front();
while(!dq.empty() && tmp[dq.back()] >= tmp[i - l])
dq.pop_back();
dq.push_back(i - l);
if(tmp[i] - tmp[dq.front()] >= EPS)
return true;
}
return false;
}
int main()
{
in >> n >> l >> u;
for(int i = 1; i <= n; i++)
in >> c[i];
for(int i = 1; i <= n; i++)
in >> t[i];
double st = 0, dr = CMAX, med;
while(st <= dr)
{
med = (st + dr) / 2;
if(check(med))
{
ans = med;
st = med + 0.001;
}
else dr = med - 0.001;
}
out << setprecision(2) << fixed << ans << '\n';
return 0;
}