Cod sursa(job #521247)

Utilizator cosmyoPaunel Cosmin cosmyo Data 11 ianuarie 2011 20:44:02
Problema Secventa 3 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <cstdio>
const int N = 30005;
int n, c[N], t[N], d[N], Q, U;
int a = 0, b = 1;
int main() {
	freopen("secv3.in", "r", stdin);
	freopen("secv3.out", "w", stdout);
	int i;
	int num = 0, nr = 0;
	scanf("%d%d%d", &n, &Q, &U);
	for(i = 1; i <= n; ++i)
		scanf("%d", &c[i]);
	for(i= 1; i <= n; ++i)
		scanf("%d", &t[i]);
	int front = 1 , back = 0;
	for(i = 1; i <= n; ++i) {
		while(back - front + 1 > U)
			nr -= c[d[front]],	num -= t[d[back]],	 ++front;
		while(back - front + 1 >= Q && (nr + c[i]) * num > nr * (num + t[i]) )
			nr -= c[d[front]],	num -= t[d[front]],	++front;
		++back;		d[back] = i;
		num += t[i];	nr += c[i];
		//printf("%d %d\n", nr, num);
		if(nr * b > num * a && back - front + 1 >= Q)
			a = nr, b = num;
	}

	printf("%lf", (double) a/b);
	return 0;
}