Cod sursa(job #83882)

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

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

int l, u, n;
int lo, hi;
double max;
int s1, s2;

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

    int i;

    scanf("%d %d %d", &n, &l, &u);
    for (i=1; i<=n; ++i)
	scanf("%d", &V[i]);
    for (i=1; i<=n; ++i)
	scanf("%d", &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];
    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 (max < (double)s1/s2)
	    max = (double)s1/s2;
    }

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

    fclose(stdin);
    fclose(stdout);

    return 0;
}