Cod sursa(job #773260)

Utilizator SteveStefan Eniceicu Steve Data 1 august 2012 11:50:00
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <fstream>

using namespace std;

int N, L, U, a;
double C[30005];
double T[30005];
double more = 0;

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) {
	int a = -1;
	double S1 = 0, S2 = 0, best = -1;
	for (int i = 0; i < L; i++)
	{
		S1 += C[i];
		S2 += T[i];
		best = max (best, S1 - S2 * K);
	}
	for (int i = L; i < N; i++)
	{
		S1 += C[i];
		S2 += T[i];
		if (i - a > U) S1 -= C[++a], S2 -= T[a];
		while (L < i - a && S1 - S2 * K < 0)
		{
			S1 -= C[++a];
			S2 -= T[a];
		}
		best = max (best, S1 - S2 * K);
	}
	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;
}