Cod sursa(job #1022826)

Utilizator ELHoriaHoria Cretescu ELHoria Data 5 noiembrie 2013 23:19:57
Problema Secventa 3 Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <fstream>
#include <cstring>
#include <algorithm>
#include <string>
 
using namespace std;
 
ifstream cin("secv3.in");
ofstream cout("secv3.out");
 

const int nmax = int(1e5) + 2;
int N, L, U;
int c[nmax], t[nmax];
int s[nmax];
int dq[nmax<<1];

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];
		s[i] = c[i] - t[i];
	}
}

void solve() {
	int l, r;
	l = 0, r = 0;
	dq[r++] = 0;
	double ret = 0.0;
	for(int i = L;i <= N;i++) {
		while(r > l && s[dq[r - 1]] <= s[i - L + 1]) {
			r--;
		}
		ret = max(ret,1.0*(c[i] - c[dq[l]])/(t[i] - t[dq[l]]));
		dq[r++] = i - L + 1;
		if(dq[l] == i - U + 1) {
			l++;
		}
	}
	cout.precision(3);
	cout<<fixed<<ret;
}
 
int main()
{
	readData();
	solve();
    return 0;
}