Cod sursa(job #88182)

Utilizator gigi_becaliGigi Becali gigi_becali Data 30 septembrie 2007 17:58:53
Problema Secventa 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <cstdio>
#include <string>
#define maxn 30001

struct nod { int p, q, poz;nod(){}; nod(int a, int b, int c){p=a; q=b; poz=c;};};

nod dq[maxn];

int n, A, B;
int a1[maxn], b1[maxn];
int a[maxn], b[maxn];
int p,q;

void read()
{
	freopen("secv3.in","r",stdin);
	scanf("%d %d %d\n", &n, &A, &B);
	int i;
	for(i=1;i<=n;++i) scanf("%d ", a+i);
	for(i=1;i<=n;++i) scanf("%d ", b+i);
	a1[1]=a[1];
	b1[1]=b[1];
	for(i=2;i<=n;++i) a1[i]=a1[i-1]+a[i];
	for(i=2;i<=n;++i) b1[i]=b1[i-1]+b[i];
}

void solve()
{
	//dq[1].p=a1[1];
	//dq[1].q=b1[1];
	//dq[1].poz=1;
	q=1;p=0;
	int i,j;
	int px=0, qx=1;
	for(i=1;i<A;++i)
	{
		while(p<=q && dq[p].p*b1[i]<dq[p].q*a1[i]) --q;
		 ++q;
		dq[q]=nod(a1[i], b1[i], i);
	}
	
	for(i=A;i<=n;++i)
	{
		
		while(p<=q && dq[p].poz+B<i) ++p;
		
		
		if((a1[i]-dq[p].p)*qx>(b1[i]-dq[p].q)*px) px=a1[i]-dq[p].p, qx=b1[i]-dq[p].q;
		
		while(p<=q && dq[p].p*b1[i]<dq[p].q*a1[i]) --q;
		 ++q;
		dq[q]=nod(a1[i], b1[i], i);
		
	//	for(int j=p;j<=q;++j) printf("%d %d %d\n", dq[j].p, dq[j].q, dq[j].poz);
	///	printf("\n");
		
		
	}
		
	
//	printf("%d %d\n", px, qx);
	freopen("secv3.out","w",stdout);
	printf("%.3lf\n", px/(double)qx);
}


int main()
{
	read();
	solve();
	//for(int i=1;i<=n;++i)printf("%d ", a1[i]);
	return 0;
}