Pagini recente » Cod sursa (job #1364831) | Cod sursa (job #492807) | Cod sursa (job #588760) | Cod sursa (job #3217668) | Cod sursa (job #1520210)
#include<bits/stdc++.h>
using namespace std;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
const int NMAX=30005;
int n,L,U,deq[NMAX];
double sol;
long long s[NMAX],t[NMAX],rez[NMAX];
//pot face problema pe int deoarece inecuatia >= o pot inmulti cu 10^2
//si cautarea binara pe inturi va fi defapt cautare binara pe double:)
int main()
{
int i,j,pr,ul,x,ok;
long long kkt,st,mij,dr;
fin>>n>>L>>U;
for (i=1;i<=n;i++)
{
fin>>x;
x*=100;
s[i]=s[i-1]+x;
}
for (i=1;i<=n;i++) fin>>x,t[i]=t[i-1]+x;
st=1;dr=3000000000;//rasp max initial*100
while (st<=dr)
{
mij=(st+dr)/2;
for (i=1;i<=n;i++) rez[i]=s[i]-1LL*mij*t[i];
pr=1;ul=ok=0;
for (i=L;i<=n;i++)
{
//pun rez[i-L]
while (ul>=pr && rez[deq[ul]]>=rez[i-L]) ul--;
deq[++ul]=i-L;
//scot pr daca e nevoie
if (deq[pr]<(i-U)) pr++;
if (rez[i]>=rez[deq[pr]]) ok=1;
}
if (ok==1)
{
sol=mij;
st=mij+1;
}
else dr=mij-1;
}
sol/=100.0;
fout<<setprecision(3)<<fixed;
fout<<sol<<"\n";
return 0;
}