Mai intai trebuie sa te autentifici.

Cod sursa(job #554940)

Utilizator EduardLEduard Luca EduardL Data 15 martie 2011 10:41:08
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <cstdio>
#define ll long long
#define N 30010

int n,lmin,lmax;
ll v1[N],v2[N];
ll v[N];
ll d[N];

inline void citire() {
	scanf("%d%d%d",&n,&lmin,&lmax);
	int x;
	for(int i=1; i<=n; ++i) {
		scanf("%d",&x);
		v1[i] = (ll)x*100LL;
		v1[i] += v1[i-1];
	}
	for(int i=1; i<=n; ++i) {
		scanf("%d",&x);
		v2[i] = (ll)x;
		v2[i] += v2[i-1];
	}
}

inline bool vezi(ll rez) {
	int p=1,u=0;

	for(int i=1; i<=n; ++i)
		v[i] = v1[i]-v2[i]*rez;

	for(int i=lmin+1; i<=n; ++i) {
		if(p<=u && i-d[p]>lmax)
			++p;
		while(p<=u && v[d[u]]>=v[i-lmin])
			--u;
		d[++u] = i-lmin;

		if(p<=u && v[d[p]]<=v[i])
			return true;
	}

	return false;
}

inline void rezolva() {
	int p=1,u=100000,m;

	while(p+1<u) {
		m = (p+u)>>1;
		if(vezi(m))
			p = m;
		else
			u = m-1;
	}

	if(vezi(p+1))
		++p;

	printf("%d.%.2d\n",p/100,p%100);
}

int main() {
	freopen("secv3.in","r",stdin);
	freopen("secv3.out","w",stdout);

	citire();
	rezolva();

	return 0;
}