Pagini recente » Cod sursa (job #198356) | Cod sursa (job #829398) | Cod sursa (job #1818793) | Cod sursa (job #1993026) | Cod sursa (job #1691137)
#include <iostream>
#include <fstream>
#include <iomanip>
#define NMAX 3005
#define eps 0.00001
#include <cstdio>
using namespace std;
ifstream f("secv3.in");
int n,l,u,cost[NMAX],timp[NMAX],ind[NMAX];
double s[NMAX],d[NMAX];
bool okay(double k)
{
int i,head=1,tail=0;
double MAX=-2000000000; s[0]=0;
for(i=1;i<=n;i++)s[i]=s[i-1]+(1.0*cost[i]-1.0*k*timp[i]);
for(i=l;i<=n;i++)
{
while(head<=tail&&ind[head]<i-u)++head;
while(head<=tail&&d[tail]>s[i-l])--tail;
tail++; d[tail]=s[i-l]; ind[tail]=i-l;
MAX=max(MAX,s[i]-s[ind[head]]);
}
return (MAX>=0);
}
void solve()
{
double st,dr,mij,sol=0; int i;
f>>n>>l>>u;
for(i=1;i<=n;i++)f>>cost[i];
for(i=1;i<=n;i++)f>>timp[i];
st=0; dr=2000;
while(st<dr+eps)
{
mij=(st+dr)/2;
if(okay(mij))
{
sol=mij;
st=mij+eps;
}
else
dr=mij-eps;
}
freopen("secv3.out","w",stdout);
printf("%.2lf\n", sol);
}
int main()
{
solve();
return 0;
}