Pagini recente » Cod sursa (job #2719648) | Cod sursa (job #811653) | Cod sursa (job #732897) | Cod sursa (job #1919299) | Cod sursa (job #741838)
Cod sursa(job #741838)
#include<iostream>
#include<fstream>
using namespace std;
ifstream in("secv3.in");
ofstream out("secv3.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() {
while(p<=ul && el[deq[ul]] <= el[deq[ul-1]])
deq[ul - 1] = deq[ul--];
}
inline void st(const int &i) {
if(p<=u && i + l - deq[p] - 1 > u)
++p;
}
bool ver(double x) {
int i;
x/=1000; 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();
if(el[i + l] - el[deq[p]] >= 0)
return true;
}
return false;
}
int main() {
int i,j,pas = 1<<30;
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 <= 1000000 && ver(j + pas))
j+=pas;
out << (double)j/1000 << "\n";
return 0;
}