Pagini recente » Clasament fminostress2012 | Clasament test123 | Clasament test_icrisop | preONI 2007, Runda 4, Clasele 11-12 | Cod sursa (job #1738386)
#include<bits/stdc++.h>
#define INF 1<<20
#define maxN 30005
using namespace std;
int n,a[maxN],b[maxN],l,u;
long long s[maxN],mid;
deque<long long> q;
int val(int x)
{
int i;
//sume partiale
for(i=1;i<=n;i++)
s[i]=s[i-1]+a[i]*100-x*b[i];
q.clear();
//min_deque
for(int i=l;i<=n;i++)
{
while(!q.empty() && s[q.back()]>=s[i-l])
q.pop_back();
q.push_back(i-l);
if((i-q.front())==u)
q.pop_front();
if((s[i]-s[q.front()])>=0) return 1;
}
return 0;
}
int main()
{
freopen("secv3.in","r",stdin);
freopen("secv3.out","w",stdout);
scanf("%d%d%d",&n,&l,&u);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(int j=1;j<=n;j++)
{
scanf("%d",&b[j]);
}
long long ls=1;
long long ld=INF;
while (ls<=ld)
{
mid=ls+(ld-ls)/2;
if (val(mid)) ls=mid+1;
else ld=mid-1;
}
printf("%.2lf\n",ld/100.0);
return 0;
}