Cod sursa(job #83885)

Utilizator ScrazyRobert Szasz Scrazy Data 12 septembrie 2007 11:49:55
Problema Secventa 3 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <stdio.h>
#define NMAX 30001

unsigned long D[NMAX], D2[NMAX], ST[NMAX], SV[NMAX];
long T[NMAX], V[NMAX], P[NMAX];

long l, u, n;
long lo, hi;
double max;
unsigned long s1, s2, maxs1, maxs2; 

int main()
{
    freopen("secv3.in","r",stdin);
    freopen("secv3.out","w",stdout);

    long i;

    scanf("%ld %ld %ld", &n, &l, &u);
    for (i=1; i<=n; ++i)
	scanf("%ld", &V[i]);
    for (i=1; i<=n; ++i)
	scanf("%ld", &T[i]);
    SV[0]=0;
    for (i=1; i<=n; ++i)
	SV[i]=SV[i-1]+V[i];
    for (i=1; i<=n; ++i)
	ST[i]=ST[i-1]+T[i];

    lo=1;
    hi=2; 
    max=(double)SV[l]/ST[l];
    maxs1=SV[l];
    maxs2=ST[l];
    P[lo]=1;
    D[lo]=SV[1];
    D2[lo]=ST[1];

    for  (i=l+1; i<=n; ++i)
    {
	if (i-P[lo]+1>u) ++lo;
	while ((double)D[hi-1]/D2[hi-1] >= (double)SV[i-l]/ST[i-l] 
		&& hi > lo) --hi;
	D[hi] = SV[i-l]; P[hi] = i-l;
	D2[hi++] = ST[i-l];
	s1=SV[i]-D[lo];
	s2=ST[i]-D2[lo];
	if ((double)maxs1/maxs2 < (double)s1/s2)
	{
	    maxs1 = s1;
	    maxs2 = s2;
	}
    }
    max = (double)maxs1/maxs2;

    printf("%.2lf", max);

    fclose(stdin);
    fclose(stdout);

    return 0;
}