Pagini recente » Cod sursa (job #3036678) | Cod sursa (job #1287312) | Cod sursa (job #623046) | Cod sursa (job #1198425) | Cod sursa (job #985045)
Cod sursa(job #985045)
#include <fstream>
#include <iomanip>
using namespace std;
ifstream f("secv3.in");
ofstream g("secv3.out");
double Cost[30002],Time[30002],Partial[30002];
int length,start,fin,C=1<<28,N,L,U,Deque[30002];
void Read()
{
int i,value;
f>>N>>L>>U;
for(i=1;i<=N;i++)
{
f>>value;
Cost[i]=value;
}
for(i=1;i<=N;i++)
{
f>>value;
Time[i]=value;
}
}
bool Calculate(double val)
{
int i;
int End=0,Begin=1;
for(i=1;i<=N;i++)
Partial[i]=Partial[i-1]+Cost[i]-Time[i]*val;
if(Partial[L]>0)
return 1;
for(i=L+1;i<=N;i++)
{
while(End>=Begin && Partial[i-L]<Partial[Deque[End]])
End--;
Deque[++End]=i-L;
if(Deque[Begin]==i-U-1)
Begin++;
if(Partial[i]>Partial[Deque[Begin]])
return 1;
}
return 0;
}
void Binary_Search()
{
double st=0,dr=1<<28,mid,sol;
while(st<=dr)
{
mid=(st+dr)/2;
if(Calculate(mid)==1)
{
sol=mid;
st=mid+0.001;
}
else
dr=mid-0.001;
}
g<<fixed<<setprecision(6)<<sol<<"\n";
}
int main()
{
Read();
Binary_Search();
return 0;
}