Pagini recente » Cod sursa (job #1325082) | Cod sursa (job #1943260) | Cod sursa (job #2191462) | Cod sursa (job #322630) | Cod sursa (job #389288)
Cod sursa(job #389288)
#include<queue>
#include<stdio.h>
using namespace std;
#define DIM 30010
int n,l,u;
int c[DIM],t[DIM];
double a[DIM];
double calc(double rez)
{
deque <int> dq;
dq.push_back(0);
double Max=-(1<<30);
for(int i=1;i<=n;i++)
a[i]=a[i-1]+c[i]-t[i]*rez;
for(int i=l;i<=n;i++)
{
if(a[i]-a[dq.front()]>Max)
Max=a[i]-a[dq.front()];
while(!dq.empty()&&a[dq.back()]>=a[i-l+1])
dq.pop_back();
dq.push_back(i-l+1);
if(dq.front()==i-u)
dq.pop_front();
}
return Max;
}
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",&c[i]);
for(int i=1;i<=n;i++)
scanf("%d",&t[i]);
double st=0,dr=1000,mij,nr;
while(dr-st>0.001)
{
mij=(st+dr)/2;
nr=calc(mij);
if(nr==0)
st=dr=mij;
else
if(nr>0)
st=mij+0.001;
else
dr=mij-0.001;
}
printf("%.2lf",dr);
return 0;
}