Cod sursa(job #992418)

Utilizator Cosmin1490Balan Radu Cosmin Cosmin1490 Data 1 septembrie 2013 19:37:14
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.4 kb
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
using namespace std;

const string file = "secv3";

const string infile = file + ".in";
const string outfile = file + ".out";

const int INF = 0x3f3f3f3f;


int N, L, U;
vector<int> cs;
vector<int> ts;


int MaxC;
int MinT;
double MaxR;

void pushb(deque<int>& d, int& cC, int& cT, int i)
{
	d.push_back(i);
	cC += cs[i];
	cT += ts[i];
}

void popf(deque<int>& d, int& cC, int& cT)
{
	int idx = d.front();
	d.pop_front();
	cC -= cs[idx];
	cT -= ts[idx];
}

void solve()
{
	deque<int> removables;
	deque<int> musts;

	int cC = 0;
	int cT = 0;

	int rC = 0;
	int rT = 0;

	for(int i = 0; i < L; i++)
	{
		pushb(musts, cC, cT, i);
	}
	MaxC = cC;
	MinT = cT;
	MaxR = (double)1 * MaxC / MinT;
	for(int i = L; i < N; i++)
	{
		pushb(musts, cC, cT, i);
		pushb(removables, rC, rT, musts.front());

		popf(musts, cC, cT);


		if((int)removables.size() > U - L)
		{
			popf(removables, rC, rT);
		}



		

		while(removables.size() > 0 )
		{

			int xC = cs[removables.front()];
			int xT = ts[removables.front()];

			if((double)1 * xC / xT > (double)1 * (cC + rC - xC)/(cT + rT - xT))
			{
				break;
			}

			popf(removables, rC, rT);
		}


		if(removables.size() > 0)
		{
			if((double)1 * rC / rT <= (double) 1 * cC / cT)
			{
				removables.clear();
				rC = 0;
				rT = 0;
			}
		}



		int newMaxC = cC + rC;
		int newMinT = cT + rT;
		double newMaxR = (double)1 * newMaxC / newMinT;
		if(newMaxR > MaxR)
		{
			MaxR = newMaxR;
			MaxC = newMaxC;
			MinT = newMinT;
		}

	}


}


int main()
{
	fstream fin(infile.c_str(), ios::in);


	fin >> N >> L >> U;
	cs.resize(N);
	ts.resize(N);

	for(int i = 0; i < N; i++)
	{
		fin >> cs[i];
	}
	for(int i = 0; i < N; i++)
	{
		fin >> ts[i];
	}

	fin.close();

	solve();

	fstream fout(outfile.c_str(), ios::out);
	fout << fixed << setprecision(3) << MaxR << "\n";
	fout.close();
}