Pagini recente » Cod sursa (job #2988413) | Cod sursa (job #1515177) | Cod sursa (job #906962) | Cod sursa (job #2735493) | Cod sursa (job #993059)
Cod sursa(job #993059)
#include <cstdio>
#include <deque>
#include <vector>
#include <algorithm>
using namespace std;
const double eps=1e-6;
int n;
int L,U;
int a[30100];
int b[30100];
bool check(double x) {
double sp[30100];
deque<int> Q;
for(int i=1;i<=n;i++) {
sp[i]=sp[i-1]+(double)a[i]-(double)b[i]*x;
}
Q.push_back(0);
for(int i=L;i<=n;i++) {
if(!Q.empty())
if(sp[i]-sp[Q.front()]>0)
return true;
while(!Q.empty()&&sp[i-L+1]-eps<sp[Q.back()])
Q.pop_back();
Q.push_back(i-L+1);
while(!Q.empty()&&i-Q.front()>=U)
Q.pop_front();
}
return false;
}
double bsearch(double st,double dr) {
double ans;
for(int stp=0;stp<60;++stp) {
double mij=(double)(st+dr)/2.0;
if(check(mij))
st=mij;
else
dr=mij;
}
return st;
}
int main() {
freopen("secv3.in","r",stdin);
freopen("secv3.out","w",stdout);
scanf("%d%d%d",&n,&L,&U);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
scanf("%d",&b[i]);
printf("%.2lf ",bsearch(0.0,30000000.0));
return 0;
}