Cod sursa(job #553408)

Utilizator zizou_adyIacov Adrian zizou_ady Data 13 martie 2011 23:44:53
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <fstream>
#include <vector>
#include <deque>
using namespace std;

#define MIN -9999999
#define MAX 9999999

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

void Read();
void Solve();

int maxim = MIN;
int minim = MAX;
double sol;
vector <int> c;
vector <int> t;

deque <int> dmax;
deque <int> dmax2;
deque <int> dmin;
deque <int> dmin2;

int n, l, u;

int main()
{
	Read();
	Solve();
	fout << sol << '\n';
	fout.close();
	fin.close();
	return 0;
}

void Read()
{
	fin >> n >> l >> u;
	t.resize(n+1);
	c.resize(n+1);
	int x;
	for (int i = 1; i <= n; ++i)
	{
		fin >> x;
		c[i] = c[i-1] + x;
	}
	for (int i = 1; i <= n; ++i)
	{
		fin >> x;
		t[i] = t[i-1] + x;
	}
}

void Solve()
{
	for (int i = 1; i <= n; ++i)
	{
		while (!dmax.empty() && c[i] >= c[dmax.back()])
		{
			dmax.pop_back();
		}
		dmax.push_back(i);
		while (!dmin.empty() && c[i] <= c[dmin.back()])
		{
			dmin.pop_back();
		}
		dmin.push_back(i);
		while (!dmax.empty() && dmax.front() >= dmin.front())
			if (dmax.size() == 1)
				dmax.clear();
			else
				dmax.pop_front();
		if (i - dmax.front() >= u )
			dmax.pop_front();
		if (i - dmin.front() >= u )
			dmin.pop_front();
		if (i >= l   && !dmin.empty() && c[dmax.front()] - c[dmin.front()-1] > maxim )
		{
			maxim = c[dmax.front()] - c[dmin.front()-1];
			minim = t[dmax.front()] - t[dmin.front()-1];
		}
		if ((double)maxim/ minim > sol)
			sol = (double)maxim/ minim;
	}
	if (l == 1)
	{
		if ((double)(c[n]-c[n-1])/(t[n]-t[n-1]) > sol)
			sol = (double)(c[n]-c[n-1])/(t[n]-t[n-1]);
	}
}