Pagini recente » Cod sursa (job #864166) | Cod sursa (job #867004) | Cod sursa (job #2876478) | Cod sursa (job #1428705) | Cod sursa (job #2212693)
#include <fstream>
#include <iomanip>
using namespace std;
ifstream in("secv3.in");
ofstream out("secv3.out");
double cost[30001],timp[30001],v[30001];
int d[30001],st=0,dr=-1,n,u,l;
inline void stanga(int i)
{
if(d[st]==i&&st<=dr)
st++;
}
inline void dreapta(int i)
{
while(st<=dr&&v[i]<=v[d[dr]])
dr--;
d[++dr]=i;
}
bool verif(double val)
{
st=0;
dr=-1;
double max1=-1000000;
int i;
for(i=1;i<=n;i++)
v[i]=cost[i]-(double)timp[i]*val+v[i-1];
for(i=1;i<=n-l;i++)
{
stanga(i-u+l-1);
dreapta(i);
if(i>=l)
max1=max(max1,v[i+l]-v[d[st]]);
}
if(max1>=0)
return 1;
return 0;
}
void cautbin()
{
double r=0,pas=1<<14;
while(pas>=0.001)
{
if(verif(r+pas))
r+=pas;
pas/=2;
}
out<<fixed<<setprecision(2)<<r;
}
int main()
{
int i;
in>>n>>l>>u;
for(i=1;i<=n;i++)
in>>cost[i];
for(i=1;i<=n;i++)
in>>timp[i];
cautbin();
return 0;
}