Cod sursa(job #803056)

Utilizator toranagahVlad Badelita toranagah Data 26 octombrie 2012 23:04:03
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <fstream>
#include <deque>
#include <algorithm>
using namespace std;

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

deque<int> dq;
void push_dq(int x);
double get_dq(int pos);
int N, l, u;
double cost[30100], timp[30100], sum[30100];
int result;
void read_input();
double binary_search();
bool check_answer(double r);


int main() {
	read_input();
	fout << binary_search();
}

void read_input() {
	fin >> N >> l >> u;
	for (int i = 1; i <= N; ++i) {
		fin >> cost[i];
	}
	for (int i = 1; i <= N; ++i) {
		fin >> timp[i];
	}
}

double binary_search() {
	double lo = 0, hi = 30000000, mid;
	while (lo + 0.001 <= hi) {
		mid = lo + (hi - lo) / 2;
		if (check_answer(mid) == true) {
			lo = mid;
		} else {
			hi = mid;
		}
	}
	return mid;
}

bool check_answer(double r) {
	dq.clear();
	double max = -0x3f3f3f3f;
	for (int i = 1; i <= N; ++i) {
		sum[i] = sum[i-1] + cost[i] - r * timp[i];
	}
	if (sum[l] >= 0) return true;
	for (int i = l + 1; i <= N; ++i) {
		push_dq(i - l);
		if (sum[i] - get_dq(i) >= 0) 
			return true;
	}
	return false;
}

void push_dq(int x) {
	while(!dq.empty() && sum[dq.back()] >= sum[x]) {
		dq.pop_back();
	}
	dq.push_back(x);
}

double get_dq(int pos) {
	while (!dq.empty() && pos - dq.front() > u) {
		dq.pop_front();
	}
	return sum[dq.front()];
}