Pagini recente » Cod sursa (job #1656843) | Cod sursa (job #2487556) | Cod sursa (job #777660) | Cod sursa (job #2534426) | Cod sursa (job #509580)
Cod sursa(job #509580)
# include <fstream>
using namespace std;
int n, l, u, c[30003], t[30003], dq[30003], sol;
long long v[30003];
int verifica (int rez);
void solve (int st, int dr);
int main ()
{
ifstream fin ("secv3.in");
fin>>n>>l>>u;
for(int i=1;i<=n;++i)
fin>>c[i], c[i]*=100;
for(int i=1;i<=n;++i)
fin>>t[i];
solve (0, 100001);
freopen("secv3.out", "w", stdout);
printf("%.2lf", sol/100.);
return 0;
}
int verifica (int rez)
{
for (int i=1;i<=n;++i)
v[i]=v[i-1]+(long long)c[i]-rez*t[i];
int st=1, dr=1;
long long suma=v[l];
dq[1]=0;
for(int i=l;i<=n;++i)
{
while (v[i-l]<=v[dq[dr]] && dr>=st)--dr;
dq[++dr]=i-l;
if (v[i]-v[dq[st]]>suma)
suma=v[i]-v[dq[st]];
while (i-dq[st]>=u)
++st;
}
if (suma>0)
return 1;
return 0;
}
void solve (int st, int dr)
{
if (st==dr)
{
if (sol<st && verifica(st))
sol=st;
return;
}
int mij=(st+dr)/2;
if (!verifica(mij))
solve(st, mij);
else
{
sol=mij;
solve(mij+1, dr);
}
}