Cod sursa(job #1022845)

Utilizator ELHoriaHoria Cretescu ELHoria Data 6 noiembrie 2013 00:01:42
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <fstream>
#include <cstring>
#include <algorithm>
#include <string>
 
using namespace std;
 
ifstream cin("secv3.in");
ofstream cout("secv3.out");
 

const double eps = 1e-3;
const int nmax = int(1e5) + 2;
int N, L, U;
int c[nmax], t[nmax];
double s[nmax];
int dq[nmax];

void readData() {
	cin>>N>>L>>U;
	for(int i = 1;i <= N;i++) {
		cin>>c[i];
		c[i] += c[i - 1];
	}
	for(int i = 1;i <= N;i++) {
		cin>>t[i];
		t[i] += t[i - 1];
	}
}

inline bool go(double k) {
	for(int i = 1;i <= N;i++ ){
		s[i] = s[i - 1] + (c[i] - c[i - 1])  - (t[i] - t[i - 1])*k;
	}
	double maxR = s[L];
	int l, r;
	l = r = 0;
	dq[r++] = 0;
	for(int i = L + 1;i <= N;i++) {
		while(r > l && s[dq[r - 1]] >= s[i - L]) r--;
		dq[r++] = i - L;
		if(dq[l] < i - U) l++;
		maxR = max(maxR,s[i] - s[dq[l]]);
	}
	return maxR >= 0;
}
 
int main()
{
	readData();
	double l = 0, r = c[N]*1.0;
	while(r - l > eps) {
		double mid = (r + l)/2.0;
		if(go(mid)) {
			l = mid;
		} else {
			r = mid;
		}
	}
	cout.precision(3);
	cout<<fixed<<l;
    return 0;
}