Cod sursa(job #205595)

Utilizator mordredSimionescu Andrei mordred Data 2 septembrie 2008 00:36:13
Problema Secventa 3 Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <stdio.h>
#define nmax 30001

int l,u,n,a[nmax],b[nmax];
int start,end,k,i,j,uk,ok;
long long s[nmax];

int main(){
 freopen("secv3.in","r",stdin);
 freopen("secv3.out","w",stdout);
 
 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]);
 a[5] = 500; b[5] = 6;
 start = 0; end = 1<<28;
 while(end-start>1)
    {
    ok = 1;
    k = (start + end) / 2;
    for(i=1;i<=n;++i)
        s[i] = s[i-1] + a[i] - b[i] * k;
    for(i=l;i<=u&&ok;++i)
        for(j=i;j<=n&&ok;++j)
            if(s[j]>=s[j-i])
                ok = 0;
    if(ok) end = (start + end) / 2;
    else start = (start + end) / 2,uk = (uk>k)?uk:k;
    }
 
 printf("%d.%02d",uk/100,uk%100);
 return 0;
}