Pagini recente » Cod sursa (job #423844) | Cod sursa (job #179623) | Cod sursa (job #1736136) | Cod sursa (job #1735567) | Cod sursa (job #1755261)
#include <cstdio>
#define NMax 30000
#define INF 1<<30
#define MIN(a,b)((a)<(b)?(a):(b))
int deque[NMax+1];
int t[NMax+1];
int a[NMax+1];
int b[NMax+1];
int N,L,U,K;
bool is_good(int X)
{
int i,j,inc,sf,ans=-INF;
for(i = 1; i <= N; ++i) t[i] = t[i-1] + a[i] - X*b[i];
inc = 0; sf = -1; ans = t[L];
for(j = L+1, i = 1; i <= K; ++i,++j)
{
while( sf>=inc && t[i] <= t[ deque[sf] ] ) --sf;
deque[++sf] = i;
if( t[j]-MIN(t[ deque[inc] ],0) > ans ) ans = t[j]-MIN(t[ deque[inc] ],0);
}
for(i = K+1, j = U+1; j <= N; ++i,++j)
{
if( t[j]-t[ deque[inc] ] > ans ) ans = t[j]-t[ deque[inc] ];
while( sf>=inc && deque[inc]<=i-K ) ++inc;
while( sf>=inc && t[i] <= t[ deque[sf] ] ) --sf;
deque[++sf] = i;
}
if(ans>=0) return 1;
return 0;
}
int main(){
freopen("secv3.in","r",stdin);
freopen("secv3.out","w",stdout);
int i,st,dr,mid,f;
scanf("%d %d %d",&N,&L,&U);
for(i = 1; i <= N; ++i) { scanf("%d",&a[i]); a[i]*=100; }
for(i = 1; i <= N; ++i) scanf("%d",&b[i]);
K = U-L+1;
for(st = 1, dr = NMax*100; st <= dr; )
{
mid = (st+dr)/2;
if( is_good(mid) ) { f = mid; st = mid+1; }
else dr = mid-1;
}
printf("%.2f\n",f/100);
return 0;
}