Cod sursa(job #2557049)

Utilizator CyborgSquirrelJardan Andrei CyborgSquirrel Data 25 februarie 2020 14:28:41
Problema Secventa 3 Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <iomanip>

using namespace std;

ifstream fin("secv3.in");
ofstream fout("secv3.out");

struct fra{
	double top=0, bot=0;
	fra(){}
	fra(double top, double bot) : top(top), bot(bot){}
	double calc(){
		if(bot == 0){
			return 0;
		}
		return top/bot;
	}
	fra addit(const fra &rhs){
		return fra(top+rhs.top, bot+rhs.bot);
	}
	fra subit(const fra &rhs){
		return fra(top-rhs.top, bot-rhs.bot);
	}
};

int n, mi, ma;
int dlt;
fra v[30041];

struct roller{
	fra sum;
	deque<int> val;
	int pushback(int next){
		sum = sum.addit(v[next]);
		val.push_back(next);
	}
	int popfront(){
		int prev = val.front();
		sum = sum.subit(v[prev]);
		val.pop_front();
		return prev;
	}
	int roll(int next){
		int prev = popfront();
		pushback(next);
		return prev;
	}
	void epicroll(int next){
		fra va = v[next];
		while(!val.empty() && sum.calc() <= va.calc()){
			popfront();
		}
		pushback(next);
		while(!val.empty() && val.size() >= dlt){
			popfront();
		}
	}
};

void read(){
	fin >> n >> mi >> ma;
	dlt = ma-mi;
	for(int i = 0; i < n; ++i){
		fin >> v[i].top;
	}
	for(int i = 0; i < n; ++i){
		fin >> v[i].bot;
	}
}

roller ext, obg;
double maxi;

int main(){
	read();
	for(int i = 0; i < mi; ++i){
		obg.pushback(i);
	}
	maxi = max(maxi, obg.sum.calc());
	for(int i = mi; i < n; ++i){
		int prev = obg.roll(i);
		ext.epicroll(prev);
		maxi = max(maxi, max(obg.sum.addit(ext.sum).calc(), obg.sum.calc()));
	}
	fout << fixed << setprecision(6);
	fout << maxi;
	return 0;
}