Pagini recente » Cod sursa (job #1091630) | Cod sursa (job #1703074) | Cod sursa (job #75487) | Cod sursa (job #1646683) | Cod sursa (job #1520204)
#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)>>1;
for (i=1;i<=n;i++) rez[i]=s[i]-1LL*mij*t[i];
pr=1;ul=1;deq[ul]=0;
ok=0;
for (i=L;i<=n;i++)
{
if (deq[pr]<(i-U)) pr++;
if (rez[i]>=rez[deq[pr]]) ok=1;
while (ul>=pr && rez[deq[ul]]>rez[i]) ul--;
deq[++ul]=i;
}
if (ok==1)
{
sol=mij;
st=mij+1;
}
else dr=mij-1;
}
sol/=100.0;
fout<<setprecision(3)<<fixed;
fout<<sol<<"\n";
return 0;
}