Pagini recente » Cod sursa (job #2912243) | Diferente pentru runda/tema_vacanta_tiberiu_popoviciu intre reviziile 2 si 1 | Cod sursa (job #3150462) | Cod sursa (job #2520145) | Cod sursa (job #2474543)
#include <bits/stdc++.h>
using namespace std;
ifstream fi("secv3.in");
ofstream fo("secv3.out");
const int NMAX=30005;
const double eps=1e-3;
int n,l,u,s[NMAX],t[NMAX],x[NMAX],y[NMAX];
double st,dr,mij,v[NMAX],sol;
deque <int> D;
int ok(double c)
{
D.clear();
for(int i=1;i<=n;i++)
v[i]=(double)s[i]-(double)t[i]*c;
for(int i=l;i<=n;i++)
{
if(!D.empty() && D.front()<i-u) D.pop_front();
while(!D.empty() && v[i-l]<=v[D.back()]) D.pop_back();
D.push_back(i-l);
if(v[i]-v[D.front()]>=0) return 1;
}
return 0;
}
int main()
{
fi>>n>>l>>u;
for(int i=1;i<=n;i++)
{
fi>>x[i];
s[i]=x[i]+s[i-1];
}
for(int i=1;i<=n;i++)
{
fi>>y[i];
t[i]=y[i]+t[i-1];
}
st=0; dr=1000;
while(dr-st>=eps)
{
mij=(st+dr)/2;
if(ok(mij))
{
sol=mij;
st=mij;
}
else dr=mij;
}
fo<<fixed<<setprecision(2)<<sol;
fi.close();
fo.close();
return 0;
}