Pagini recente » Cod sursa (job #1511871) | Cod sursa (job #856787) | Cod sursa (job #28207) | Cod sursa (job #1927314) | Cod sursa (job #741631)
Cod sursa(job #741631)
#include<iostream>
#include<fstream>
using namespace std;
ifstream in("secventa3.in");
ofstream out("secventa3.out");
const int N = 30100;
int n,l,u,c[N],d[N],deq[N], p , ul;
double el[N];
inline void add(const int &i) {
deq[++ul] = i;
}
inline void dr(const int &i) {
while(p<=ul && el[deq[ul]] > el[i])
deq[ul - 1] = deq[ul--];
}
inline void st(const int &i) {
if(i + l - deq[p] + 1 > u)
++p;
}
bool ver(double x) {
int i;
double smax = -1;
x/=100; p = 1; ul = 0;
for(i = 1; i<=n; ++i)
el[i] = (double)c[i] - d[i]*x + el[i-1];
for(i = 1; i<=n-l; ++i) {
st(i);
add(i);
dr(i);
if(el[i + l] - el[deq[p]] > smax)
smax = el[i+l] - el[deq[p]];
}
return smax>=0;
}
int main() {
int i,j,pas = 1<<19;
in >> n >> l >> u;
for(i = 1; i<=n; ++i)
in >> c[i];
for(j = 1; j<=n; ++j)
in >> d[j];
for(j = 0; pas!=0; pas>>=1)
if(j + pas <= 100000 && ver(j + pas))
j+=pas;
out << (double)j/100 << "\n";
return 0;
}