Cod sursa(job #545581)

Utilizator judgment7Andrei Aldea judgment7 Data 3 martie 2011 17:15:14
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<deque>
#include<queue>
#include<set>
#include<vector>
using namespace std;

#define II inline
#define LL long long
#define PII pair<int, int>
#define PDD pair<double, double>
#define fs first
#define ss second
#define mp make_pair
#define pb push_back
#define FOR(i, a, b) 	for(int i = a ; i <= b ; i++)
#define IFOR(i, a, b) 	for(int i = a ; i >= b ; i--)
#define FORIT(it, V) 	for(vector<int> :: iterator it = V.begin() ; it != V.end() ; it++)
#define all(a) a, a + 

const char IN[] = {"secv3.in"};
const char OUT[] = {"secv3.out"};
const int INF = 1000000005;
const double PI  = 3.14159265;
const LL NMAX = 30005;
const LL VALMAX = 1005 * 100;

LL N, L, U;
LL a[NMAX], b[NMAX];

void citi()
{
	scanf("%d%d%d", &N, &U, &L);
	FOR(i, 1, N)	scanf("%lld", &a[i]), a[i] *= 100;
	FOR(i, 1, N)	scanf("%lld", &b[i]);
}

bool exista(LL x)
{
	LL A[NMAX], S[NMAX] = {0};
	copy(a, a + NMAX, A);
	FOR(i, 1, N)
	{
		A[i] -= b[i] * x;
		S[i] = S[i - 1] + A[i];
	}
	
	deque<LL> Dq;
	FOR(i, U + 1, N)
	{
		if(Dq.size() && Dq.front() < i - L)	
			Dq.pop_front();
		while(Dq.size() && S[i - U] <= S[Dq.back()])
			Dq.pop_back();
		Dq.push_back(i - U);
		
		if(S[i] - S[Dq.front()] >= 0)
			return 1;		
	}
	
	return 0;
}

LL caut_bin()
{
	LL REZ = 0, pas;
	for(pas = 1 ; pas < VALMAX ; pas <<= 1);
	for(; pas ; pas >>= 1)
		if(REZ + pas <= VALMAX && exista(REZ + pas))
			REZ += pas;
	return REZ;
}

int main()
{
	freopen(IN, "r", stdin);
	freopen(OUT, "w", stdout);
	citi();
	printf("%.2lf\n", (double)caut_bin()/100);
	return 0;
}