Cod sursa(job #773163)

Utilizator SteveStefan Eniceicu Steve Data 1 august 2012 07:39:49
Problema Secventa 3 Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <fstream>

using namespace std;

int N, L, U, a;
int C[30005];
int 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], C[i] *= 100;
	for (int i = 0; i < N; i++)
		fin >> T[i];
	fin.close ();
}

int Good (int K) {
	int a = -1, S1 = 0, S2 = 0;
	for (int i = 0; i < N; i++)
	{
		S1 += C[i];
		S2 += T[i];
		if (i - a >= U) S1 -= C[a], S2 -= T[a++];
		if (S1 / S2 - K < 0) S1 = 0, S2 = 0, a = i;
		else if (i - a >= L) return 1;
	}
	return 0;
}

int B_Search () {
	int i = 0, step = 1 << 20;
	for (; step; step >>= 1)
		if (i + step <= 1000000 && Good (i + step)) i += step;
	return i;
}

void Scriere () {
	ofstream fout ("secv3.out");
	int a = B_Search ();
	fout << a / 100 << "." << a % 100;
	fout.close ();
}

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