Cod sursa(job #316442)

Utilizator CezarMocanCezar Mocan CezarMocan Data 19 mai 2009 18:40:15
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <cstdio>
#include <cstring>
#define maxn 30100

using namespace std;

int c[maxn], t[maxn];
int n, i, j, l, u;
double p[maxn], sum[maxn], rez;
int deq[maxn], sus, jos;


inline bool posibil(double d) {
	int i, j;
	for (i = 1; i <= n; i++)
		p[i] = c[i] - (t[i] * d);

	for (i = 1; i <= n; i++)
		sum[i] = sum[i - 1] + p[i];

	sus = 0; jos = 1;
	memset(deq, 0, sizeof(deq));
	for (i = 1; i <= n; i++) {
		if (i - l > 0) {
			while (sum[i - l] < sum[deq[sus]] && sus >= jos)
				sus--;
			sus++;
			deq[sus] = i - l;
		}
		while (deq[jos] <= i - u && jos <= sus)
			jos++;
		if (sum[i] - sum[deq[jos]] >= 0)
			return true;
	}

	return false;

}

void bsearch(double left, double right) {
	double m;
	while (left + 0.0001 <= right) {
		m = (left + right) / 2;
//		printf("%.3lf\n %d", m, posibil(m));
		if (posibil(m)) {
			if (m > rez)
				rez = m;
			left = m + 0.001;
		}
		else
			right = m - 0.001;
	}
}

int main() {
	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", &c[i]);
	for (i = 1; i <= n; i++)
		scanf("%d", &t[i]);

	bsearch(0, 30000000);

//	printf("%d\n", posibil(2.5));

	printf("%.2lf\n", rez);

	return 0;
}