Cod sursa(job #1249281)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 26 octombrie 2014 19:36:21
Problema Secventa 3 Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <deque>
#define DIM 30005
#define INF 1500000000
#define eps 0.001
#define infile "secv3.in"
#define outfile "secv3.out"

using namespace std;

ifstream f(infile);
ofstream g(outfile);

deque<int> DEQ;

double Partial_Sum[DIM], Cost[DIM], Time[DIM];

int n, l, u;

bool Check_Time(double time_to_check) {
	for (int i = 1; i <= n; ++i)
		Partial_Sum[i] = Partial_Sum[i - 1] + Cost[i] - Time[i] * time_to_check;
	if (Partial_Sum[l] > 0)
		return 1;
	DEQ.clear();
	for (int i = l; i <= n; ++i) {
		while (!DEQ.empty() && Partial_Sum[DEQ.back()] >= Partial_Sum[i - l])
			DEQ.pop_back();
		DEQ.push_back(i - l);
		while (!DEQ.empty() && DEQ.front() < i - u)
			DEQ.pop_front();
		if (Partial_Sum[i] - Partial_Sum[DEQ.front()] > 0)
			return 1;
	}
	return 0;
}

int main() {
	f >> n >> l >> u;
	for (int i = 1; i <= n; ++i)
		f >> Cost[i];
	for (int i = 1; i <= n; ++i)
		f >> Time[i];
	double left = 0, right = INF, SOL;
	while (left <= right) {
		double mid = (left + right) / 2;
		if (Check_Time(mid)) {
			left = mid + eps;
			SOL = mid;
		}
		else
			right = mid - eps;
	}
	g << setprecision(3) << SOL;
	return 0;
}

//Trust me, I'm the Doctor!