Cod sursa(job #48703)

Utilizator amadaeusLucian Boca amadaeus Data 4 aprilie 2007 23:59:53
Problema Secventa 3 Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <cstdio>
#include <deque>

using namespace std;

#define NX 30042

long long t[ NX ], s[ NX ], b[ NX ];
deque< int > Q;
int N, L, U, res;

void cit() {
	int i;
	long long x;
	
	scanf( "%d%d%d", &N, &L, &U );
	for( i = 1; i <= N; i++ ) {
		scanf( "%lld", &x );
		s[i] = s[i-1] + x;
	}
	for( i = 1; i <= N; i++ ) {
		scanf( "%lld", &x );
		t[i] = t[i-1] + x;
	}
	for( i = 1; i <= N; i++ )
		s[i] *= 100;
}

bool pred( int X ) {
	int i;

	b[0] = 0;
	for( i = 1; i <= N; i++ )
		b[i] = s[i] - X * t[i];

	Q.clear();
	for( i = 1; i <= N-L+1; i++ ) {
		while( !Q.empty() && Q.front() < i-U+L-1 )
			Q.pop_front();
		while( !Q.empty() && b[ Q.back() ] > b[ i-1 ] )
			Q.pop_back();
		Q.push_back( i-1 );
		if( b[ i+L-1 ] >= b[ Q.front() ] )
			return true;
	}
	return false;
}

int bs( int lo, int hi ) {
	int step, i;

	for( step = 1; step < (hi - lo); step <<= 1 );

	for( i = lo - 1; step; step >>= 1 )
		if( i + step <= hi )
			if( pred( i + step ) )
				i += step;
	return i;
}

void rez() {
	res = bs( 1, 100000 );
}

void scr() {
	printf( "%d.%0d\n", res / 100, res % 100 );
}

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

	cit();
	rez();
	scr();

	return 0;
}