Pagini recente » Cod sursa (job #167120) | Cod sursa (job #2664723) | Cod sursa (job #2511613) | Cod sursa (job #714393) | Cod sursa (job #2976266)
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
const int Nmax=30005;
int c[Nmax],t[Nmax],sc[Nmax],st[Nmax];
double ideal[Nmax];
deque<int> dq;
int main()
{
int n,l,u;
fin>>n>>l>>u;
for(int i=1;i<=n;i++)
{
fin>>c[i];
sc[i]=sc[i-1]+c[i];
}
for(int i=1;i<=n;i++)
{
fin>>t[i];
st[i]=st[i-1]+t[i];
}
double left=0.0,r=1000.0;
double mid,sol;
while(left<r)
{
mid=(r+left)/2;
int ok=0;
for(int i=1;i<=n;i++)
{
ideal[i]=1.0*st[i]-(sc[i]/mid);
}
dq.clear();
for(int i=l;i<=n;i++)
{
while(!dq.empty() && ideal[i-l]>ideal[dq.back()])
{
dq.pop_back();
}
dq.push_back(i-l);
if(dq.front()<i-u)
{
dq.pop_front();
}
if(ideal[i]-ideal[dq.front()]==0)
{
ok=2;
break;
}
if(ideal[i]-ideal[dq.front()]<=0)
{
ok=1;
}
}
if(ok==2)
{
sol=mid;
left=mid+1;
}
if(ok==1)
{
left=mid;
}
if(ok==0)
{
r=mid;
}
}
fout<<sol;
return 0;
}