Pagini recente » Cod sursa (job #929244) | Cod sursa (job #1597601) | Cod sursa (job #2724447) | Cod sursa (job #667231) | Cod sursa (job #1139518)
#include <iostream>
#include<stdio.h>
#include<deque>
using namespace std;
FILE *f,*g;
deque<int> mini;
float val[30001];
int cost[30001],timp[30001],U,L,n;
void add(int a)
{
while (!mini.empty()&&val[mini.back()]>val[a]) mini.pop_back();
mini.push_back(a);
}
int uberadd(int a)
{
int q=mini.front();
if (q==a-U+L-1) mini.pop_front();
add(a);
return q;
}
void initialization(void)
{
int i;
mini.clear();
for(i=0;i<=U-L;i++) add(i);
}
void create(float x)
{
int i;
for(i=1;i<=n;i++)
{
val[i]=(cost[i]-x*timp[i])+val[i-1];
}
}
bool verify(void)
{
int i,q;
initialization();
for(i=U-L+1;i<=n-L+1;i++)
{
q=uberadd(i);
if (val[i+L-1]-val[q]>=0) return 1;
}
return 0;
}
float binsearch(void)
{
float left=0,right=1000,mid;
while(right-left>=0.01)
{
mid=(left+right)/2;
create(mid);
if (verify()) left=mid;
else right=mid;
}
return left;
}
int main()
{
int i;
f=fopen("secv3.in","r");
g=fopen("secv3.out","w");
fscanf(f,"%d%d%d",&n,&L,&U);
for(i=1;i<=n;i++) fscanf(f,"%d",&cost[i]);
for(i=1;i<=n;i++) fscanf(f,"%d",&timp[i]);
fprintf(g,"%lf",binsearch());
return 0;
}