Pagini recente » Cod sursa (job #3153902) | Cod sursa (job #57318) | Cod sursa (job #2785213) | Cod sursa (job #35022) | Cod sursa (job #3153877)
#include <fstream>
#define div 100
using namespace std;
ifstream cin("secv3.in");
ofstream cout("secv3.out");
int sp1[30001],sp2[30001];
struct ura
{
int ind,rez;
}dq[30001];
int main()
{
int n,l,u,i,j1,j2,st=0,dr=1e5,mij,poz,ok,sum;
cin>>n>>l>>u;
for(i=1;i<=n;i++)
{
cin>>sp1[i];
sp1[i]+=sp1[i-1];
}
for(i=1;i<=n;i++)
{
cin>>sp2[i];
sp2[i]+=sp2[i-1];
}
while(st<=dr)
{
mij=(st+dr)>>1;
ok=0;
dq[1].ind=0;
dq[1].rez=0;
for(j1=1,j2=1,i=l;i<=n&&ok==0;i++)
{
if(dq[j1].ind<i-u)
j1++;
sum=sp1[i-l]*div-sp2[i-l]*mij;
while(j2>=j1&&dq[j2].rez>=sum)
j2--;
j2++;
dq[j2].rez=sum;
dq[j2].ind=i-l;
if(sp1[i]*div-sp2[i]*mij-dq[j1].rez>=0)
ok=1;
}
if(ok==0)
dr=mij-1;
else
{
poz=mij;
st=mij+1;
}
}
cout<<(double)poz/div;
return 0;
}