Pagini recente » Cod sursa (job #2357914) | Cod sursa (job #1066521) | Cod sursa (job #1143776) | Cod sursa (job #2530046) | Cod sursa (job #990947)
Cod sursa(job #990947)
#include <cstdio>
#include <deque>
#include <vector>
#include <algorithm>
using namespace std;
const double err=0.01;
int n;
int L,U;
int a[30100];
int b[30100];
bool check(double x) {
double v[30100];
double sp[30100];
deque<int> Q;
for(int i=1;i<=n;i++) {
v[i]=(double)a[i]-(double)b[i]*x;
sp[i]=sp[i-1]+v[i];
}
Q.push_back(0);
for(int i=L;i<=n;i++) {
while(!Q.empty()&&i-Q.front()>=U)
Q.pop_front();
if(!Q.empty())
if(sp[i]-sp[Q.front()]>0)
return true;
while(!Q.empty()&&sp[i-L+1]<=sp[Q.back()])
Q.pop_back();
Q.push_back(i-L+1);
}
return false;
}
double bsearch(int st,int dr) {
double ans;
while(st<dr) {
double mij=(double)(st+dr)/200.0;
//fprintf(stderr,"%d ",mij);
if(check(mij)) {
st=((st+dr)>>1)+1;
ans=mij;
}
else
dr=((st+dr)>>1)-1;
}
return ans;
}
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,(1<<30)));
return 0;
}