Cod sursa(job #316389)

Utilizator savimSerban Andrei Stan savim Data 19 mai 2009 13:44:35
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <stdio.h>

#define MAX_N 30010

int n, l, u, i, ok, p, q;
int A[MAX_N], B[MAX_N], deq[MAX_N];
double sum[MAX_N];
double st, dr, mid, sol;

void cit() {
	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]);
	for (i = 1; i <= n; i++)
		scanf("%d", &B[i]);
}

void deq_push(int i) {
	deq[++q] = i;
	while (sum[deq[q]] > sum[deq[q - 1]] && q > p) {
		deq[q - 1] = deq[q];
		deq[q--] = 0;
	}
}

void deq_pop(int i) {
	while (deq[p] < i && p <= q)
		p++;
}

void solve() {
	st = 0; dr = 1000000000;
	while (st + 0.0001 < dr)	{
		mid = (double) (st + dr) / 2;

        for (i = 1; i <= n; i++)
			sum[i] = (double) sum[i - 1] + A[i] - mid * B[i];

		p = 1; q = 0;
		for (i = l; i <= u; i++)
		   deq_push(i);	
		
		ok = 0;
		for (i = 1; i <= n; i++) {
            if (sum[deq[p]] >= sum[i - 1]) {
				ok = 1;
				break;
			}

			deq_pop(i + l);
			if (i + u <= n) 
				deq_push(i + u);

			if (p > q) break;
		}

		if (ok) {
			if (mid > sol) sol = mid;
			st = mid;
		}
		else dr = mid;
	}

	printf("%.3lf\n", sol);
}

int main() {

    cit();
	solve();
	
	return 0;
}