Cod sursa(job #773575)

Utilizator SteveStefan Eniceicu Steve Data 2 august 2012 06:26:51
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <fstream>
#include <queue>

using namespace std;

int N, L, U, a;
double C[30005];
double T[30005];
double dog[30005];
double more = 0;
deque <int> dq;

#define pb(a) push_back (a)
#define dog (dog + 1)

void Citire () {
	ifstream fin ("secv3.in");
	fin >> N >> L >> U;
	for (int i = 0; i < N; i++)
		fin >> C[i];
	for (int i = 0; i < N; i++)
		fin >> T[i];
	fin.close ();
}

int Good (double K) {
	double best = -1;
	dog[-1] = 0;
	for (int i = 0; i < N; i++)
		dog[i] = C[i] - K * T[i] + dog[i - 1];
	dq.clear ();

	for (int i = L - 1; i < N; i++)
	{
		while (!dq.empty () && dog[dq.back ()] > dog[i - L]) dq.pop_back ();
		dq.pb (i - L);
		
		while (!dq.empty () && i - dq.front () > U) dq.pop_front ();
		
		best = max (best, dog[i] - dog[dq.front ()]);
	}
	return best > 0;
}

double B_Search () {
	double i = 0, step = 1024;
	for (; step >= 0.0001; step /= 2)
		if (Good (i + step)) i += step;
	return i;
}

void Scriere () {
	ofstream fout ("secv3.out");
	fout << B_Search ();
	fout.close ();
}

int main () {
	Citire ();
	Scriere ();
	return 0;
}