Cod sursa(job #741838)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 27 aprilie 2012 10:07:19
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include<iostream>
#include<fstream>
using namespace std;

ifstream in("secv3.in");
ofstream out("secv3.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() {
	while(p<=ul && el[deq[ul]] <= el[deq[ul-1]])
		deq[ul - 1] = deq[ul--];
}

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

bool ver(double x) {
	int i;
	x/=1000; 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();
		
		if(el[i + l] - el[deq[p]] >= 0)
			return true;
	}
	return false;
}

int main() {
	int i,j,pas = 1<<30;
	
	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 <= 1000000 && ver(j + pas))
			j+=pas;
	
	out << (double)j/1000 << "\n";
	
	return 0;
}