Cod sursa(job #494175)

Utilizator klamathixMihai Calancea klamathix Data 20 octombrie 2010 21:30:30
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include<cstdio>
#include<algorithm>
#include<set>
const double inf = 100000000.00;
const int maxn = 30005;
using namespace std;

int i , j , v[maxn] , w[maxn] , L, U , n;
double b[maxn] , sum[maxn];
		

bool possible ( double c ) {
	int i , j;
	set <double> S;
	
	for( i = 1 ; i <= n ; ++i ) 
		b[i] = v[i] - c * w[i];
	for( i = 1 ; i <= n ; ++i ) 
		sum[i] = sum[i - 1] + b[i];
	for( i = L ; i <= n ; ++i ) {
		S.insert(sum[i - L]);
		if ( sum[i] - *S.begin() >= 0 ) return true;
		if ( i >= U ) S.erase(sum[i - U]);
	}
	return false;
}

double solve() {
	double lf , rt , mid , sol = -1, i;
	for( lf = 0 , rt = 1024 , i = 1 ; i <= 20 ; ++i ) {
		mid = ( lf + rt ) * 0.5;
		if ( possible( mid ) ) sol = mid , lf = mid;
			else rt = mid;
	}
return sol;
}

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",&v[i]);
	for( i = 1 ; i <= n ; ++i)
		scanf("%d",&w[i]);
	
	printf("%.3lf",solve());
	
return 0;
}