Pagini recente » Cod sursa (job #1329630) | Cod sursa (job #2395863) | Cod sursa (job #2473212) | Cod sursa (job #620003) | Cod sursa (job #990924)
Cod sursa(job #990924)
#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(sp[i]-sp[Q.front()]>0)
return true;
while(!Q.empty()&&sp[i]<=sp[Q.back()])
Q.pop_back();
Q.push_back(i);
}
return false;
}
double bsearch(double st,double dr) {
while(st<dr) {
double mij=(st+dr)/2.0;
//fprintf(stderr,"%d ",mij);
if(check(mij)) {
st=mij;
}
else
dr=mij-err;
}
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,30000000.00));
return 0;
}