Pagini recente » Cod sursa (job #477115) | Cod sursa (job #2305257)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("secv3.in");
ofstream fout ("secv3.out");
int const NMAX = 30003;
double const eps = 0.00001;
int timp [NMAX + 3], cost [NMAX + 3];
int N, L, U;
double ans, pls;
double V [NMAX + 3], sp [NMAX + 3], poz [NMAX + 3];
bool valid (double X){
deque <int> Diqu;
for (int i = 1 ; i <= N ; i ++)V [i] = timp [i] - cost [i] * X;
for (int i = 1 ; i <= N ; i ++)sp [i] = sp [i - 1] + V [i];
for (int i = 1 ; i <= N ; i ++){
while (0 < Diqu.size () && sp [i] <= sp [Diqu.back ()])
Diqu.pop_back ();
Diqu.push_back (i);
while (0 < Diqu.size () && Diqu.front () <= i - U + L - 1)
Diqu.pop_front ();
poz [i] = sp [Diqu.front()];
}
for (int i = 1 ; i <= N - L ; i ++)
if (sp [i + L] - poz [i] >= 0)return 1;
return 0;
}
int main (){
fin >> N >> L >> U;
for (int i = 1 ; i <= N ; i ++)fin >> timp [i];
for (int i = 1 ; i <= N ; i ++)fin >> cost [i];
for (pls = (1 << 21) ; eps < pls; pls /= 2)
if (valid (ans + pls))ans += pls;
fout << ans;
return 0;
}