Pagini recente » Cod sursa (job #2081039) | Cod sursa (job #2447783) | Cod sursa (job #954141) | Cod sursa (job #2290761) | Cod sursa (job #977426)
Cod sursa(job #977426)
#include <fstream>
#include <iomanip>
using namespace std;
ifstream f("secv3.in");
ofstream g("secv3.out");
double Cost[30002],Time[30002],Partial[30002];
double maximum=-1000000001;
double Max=-1;
int length,start,fin,C=1<<20,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;
for(i=L;i<=N;i++)
{
while(End>=Begin && Partial[i]<Partial[Deque[End]])
End--;
Deque[++End]=i-L;
if(Deque[Begin]==i-U)
Begin++;
if(Partial[i]>Partial[Deque[Begin]])
return 1;
}
return 0;
}
void Binary_Search()
{
double st=0,dr=(double)C,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(4)<<sol<<"\n";
}
int main()
{
Read();
Binary_Search();
return 0;
}