Cod sursa(job #741631)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 26 aprilie 2012 16:56:51
Problema Secventa 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include<iostream>
#include<fstream>
using namespace std;

ifstream in("secventa3.in");
ofstream out("secventa3.out");

const int N = 30100;

int n,l,u,c[N],d[N],deq[N], p , ul;
double el[N];

inline void add(const int &i) {
	deq[++ul] = i;
}

inline void dr(const int &i) {
	while(p<=ul && el[deq[ul]] > el[i])
		deq[ul - 1] = deq[ul--];
}

inline void st(const int &i) {
	if(i + l - deq[p] + 1 > u)
		++p;
}

bool ver(double x) {
	int i;
	double smax = -1;
	x/=100; p = 1; ul = 0;
	
	for(i = 1; i<=n; ++i)
		el[i] = (double)c[i] - d[i]*x + el[i-1];
	
	for(i = 1; i<=n-l; ++i) {
		st(i);
		add(i);
		dr(i);
		
		if(el[i + l] - el[deq[p]] > smax)
			smax = el[i+l] - el[deq[p]];
	}
	return smax>=0;
}

int main() {
	int i,j,pas = 1<<19;
	
	in >> n >> l >> u;
	
	for(i = 1; i<=n; ++i)
		in >> c[i];
	
	for(j = 1; j<=n; ++j)
		in >> d[j];
	
	for(j = 0; pas!=0; pas>>=1)
		if(j + pas <= 100000 && ver(j + pas))
			j+=pas;
	
	out << (double)j/100 << "\n";
	
	return 0;
}