Cod sursa(job #83881)

Utilizator ScrazyRobert Szasz Scrazy Data 12 septembrie 2007 11:05:12
Problema Secventa 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <stdio.h>
#define NMAX 30001
#define INF 1000000000

long double D[NMAX], S[NMAX];
int T[NMAX], V[NMAX], P[NMAX];

int l, u, n;
int lo, hi;
long double max;

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]);
    S[0]=0;
    for (i=1; i<=n; ++i)
	S[i]=S[i-1]+(long double)V[i]/T[i];

    lo=1;
    hi=2; 
    max=S[l];
    P[lo]=1;
    D[lo]=S[1];

    for  (i=l+1; i<=n; ++i)
    {
	if (i-P[lo]+1>u) ++lo;
	while (D[hi-1] >= S[i-l] && hi > lo) --hi;
	D[hi] = S[i-l]; P[hi++] = i-l;
	if (max < S[i]-D[lo])
	    max = S[i]-D[lo];
    }

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

    fclose(stdin);
    fclose(stdout);

    return 0;
}