Pagini recente » Cod sursa (job #3323037) | Cod sursa (job #3316966) | Cod sursa (job #3329511) | Cod sursa (job #3321596) | Cod sursa (job #3350494)
#include <fstream>
#include <iomanip>
#include <deque>
using namespace std;
ifstream in("secv3.in");
ofstream out("secv3.out");
const int NMAX=3e4+5;
const double PMAX=16777216, PMIN=0.0078125;
int n, l, u, x, sc[NMAX], st[NMAX];
deque<int> dq;
double func(int i, double r)
{
return sc[i]-r*st[i];
}
bool check(double r)
{
dq.clear();
for(int j=1;j<=n-l+1;j++)
{
while(!dq.empty() && func(j-1, r)<=func(dq.front(), r))
dq.pop_front();
dq.push_front(j);
while(!dq.empty() && dq.back()<j-u+l)
dq.pop_back();
if(!dq.empty() && func(dq.back()-1, r)<=func(j+l-1, r))
return 1;
}
return 0;
}
double caut_bin()
{
double r=0, pas=PMAX;
while(pas>=PMIN)
{
if(check(r+pas))
r+=pas;
pas/=2;
}
return r;
}
int main()
{
in>>n>>l>>u;
for(int i=1;i<=n;i++)
{
in>>x;
sc[i]=sc[i-1]+x;
}
for(int i=1;i<=n;i++)
{
in>>x;
st[i]=st[i-1]+x;
}
out<<fixed<<setprecision(4)<<caut_bin();
return 0;
}