Cod sursa(job #203083)

Utilizator andrei.12Andrei Parvu andrei.12 Data 13 august 2008 16:02:10
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include<stdio.h>

#define lg 30005
#define lint long long

int n, i, u, l;
lint v[lg], w[lg];
double rezultat;

struct deq{
	lint v;
       	int i;
};
deq q[lg];

inline lint max(lint a, lint b){
	return a > b ? a : b;
}
bool check(lint val){
	int i, st = 1, end = 0, j;
	lint rez, d[lg] = {0};
	
	for (i = 1; i <= n; i ++){
		d[i] = d[i-1] + v[i] - w[i]*val;

//		printf("%d ", v[i] - w[i]*val);
	}

	for (i = u; i <= l; i ++){
		while (st <= end && d[i] >= q[end].v)
			end --;
		q[++end].v = d[i];
		q[end].i = i;
	}

	rez = q[1].v;
	for (i = l+1; i <= n; i ++){
		if (st <= end && q[st].i == i-l+u-1)
			st ++;
		while (st <= end && d[i] >= q[end].v)
			end --;
		q[++end].v = d[i];
		q[end].i = i;

		rez = max(rez, q[st].v - d[i-l]);
	}
	for (i = n-l+1, j = n-(l-u); i < n; i ++, j ++){
		if (st <= end && q[st].i == j)
			st ++;

		if (st <= end)
			rez = max(rez, q[st].v - d[i]);
	}

//	printf("%d\n", rez);
	if (rez >= 0)
		return 1;
	return 0;
}
lint bs(){
	lint li = 1, ls = 2000000000, x, gs = 0;

	while (li <= ls){
		x = (li+ls) / 2;
//		printf("%d\n", x);
		if (check(x)){
			gs = x;
			li = x+1;
		}
		else
			ls = x-1;
	}

	return gs;
}
int main()
{
	freopen("secv3.in", "rt", stdin);
	freopen("secv3.out", "wt", stdout);

	scanf("%d%d%d", &n, &u, &l);
	for (i = 1; i <= n; i ++){
		scanf("%lld", &v[i]);
		v[i] *= 100;
	}
	for (i = 1; i <= n; i ++)
		scanf("%lld", &w[i]);

	rezultat = (double)bs();

//	printf("%d\n", check(83));
	
	printf("%.2lf\n", rezultat / 100);

	return 0;
}