Cod sursa(job #386951)

Utilizator Mishu91Andrei Misarca Mishu91 Data 26 ianuarie 2010 13:15:09
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <cstdio>
#include <deque>

using namespace std;

#define MAX_N 30000

#define val first
#define poz second

int N, L, U, M;
int A[MAX_N], B[MAX_N], C[MAX_N];
long long S[MAX_N];

void citire()
{
	scanf("%d %d %d",&N, &L, &U);
	
	for(int i = 1; i <= N; ++i)
	{
		scanf("%d",A+i);
		A[i] *= 100;
		
		M = max(M, A[i]);
	}
	
	M *= 10;
	
	for(int i = 1; i <= N; ++i)
		scanf("%d",C+i);
}

int search(int K)
{
	long long ANS = -M;
	
	for(int i = 1; i <= N; ++i)
		S[i] = S[i-1] + A[i] - K*C[i];
	
	deque <pair<long long, int> > Q;  

	for(int i = L; i <= N; ++i)  
	{  
		while(!Q.empty() && Q.back().val > S[i - L]) Q.pop_back();  
		while(!Q.empty() && Q.front().poz < i - U) Q.pop_front();  

		Q.push_back(make_pair(S[i - L], i - L));  

		if(S[i] - Q.front().val > ANS)  
			ANS = S[i] - Q.front().val;  
	}  
	
	return (ANS > 0);
}

void solve()
{
	int i, lg;
	
	for(lg = 1; lg <= M; lg <<= 1);
	
	for(i = 0; lg; lg >>= 1)
		if(i + lg <= M && search(i + lg))
			i += lg;
	
	double rez = (double) i / 100;
	printf("%.2f\n",rez);
}

int main()
{
	freopen("secv3.in","rt",stdin);
	freopen("secv3.out","wt",stdout);
	
	citire();
	solve();
}