Pagini recente » Cod sursa (job #1407320) | Cod sursa (job #3222930)
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
const int N=200'000;
int n,l,r;
double timp[N+1],sum[N+1];
double calc(int poz,double x)
{
return -x*timp[poz]+sum[poz];
}
bool is_good(double x)
{
deque<int>d;
d.pb(0);
for(int i=l;i<=n;i++)
{
if(d.front() == i-r-1)
{
d.pop_front();
}
if(calc(i,x)>=calc(d.front(),x))
{
return true;
}
while(d.size() && calc(d.back(),x) >= calc(i-l+1,x))
{
d.pop_back();
}
d.push_back(i-l+1);
}
return false;
}
int main()
{
ifstream cin("secv3.in");
ofstream cout("secv3.out");
cin>>n>>l>>r;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
sum[i]=sum[i-1]+x;
}
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
timp[i]=timp[i-1]+x;
}
double l=0,r=sum[n];
while(r-l>=0.01)
{
double m=(l+r)/2;
if(is_good(m))
{
l=m;
}
else
{
r=m;
}
}
cout<<fixed<<setprecision(3)<<r;
return 0;
}