Pagini recente » Istoria paginii utilizator/vladd | Cod sursa (job #2631578)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
const int nmax = 30000;
const double EPS=1e-3;
int n, l, u, c[nmax + 5], t[nmax + 5], spc[nmax + 5], spt[nmax + 5];
double a[nmax + 5];
deque <int> d;
bool Check(double mid)
{
d.clear();
for (int i = 1; i <= n; ++i)
{
a[i] = (double)spc[i] - (double)(spt[i] * mid);
}
for (int i = l; i <= n; ++i)
{
if(d.size() > 0 && d.front() < i - u) d.pop_front();
while (d.size() > 0 && a[i - l] <= a[d.back()]) d.pop_back();
d.push_back(i - l);
if (a[i] - a[d.front()] >= 0) return true;
}
return false;
}
int main()
{
fin >> n >> l >> u;
for (int i = 1; i <= n; ++i)
{
fin >> c[i];
spc[i] = c[i] + spc[i - 1];
}
for (int i = 1; i <= n; ++i)
{
fin >> t[i];
spt[i] = t[i] + spt[i - 1];
}
double st = 0, dr = 1000, last = 0;
for (int i = 1; i <= 100; ++i)
{
double mij = (st + dr) / 2;
if(Check(mij) == 1) {
st = mij;
last = mij;
}
else {
dr = mij;
}
}
fout << fixed << setprecision(2) << last << "\n";
fin.close();
fout.close();
return 0;
}