Cod sursa(job #1472893)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 17 august 2015 23:23:19
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <deque>
#include <numeric>
#include <algorithm>
using namespace std;

bool exista_subsecv_pozitiva_de_lung_intre(const vector<float>& v, const int l, const int u){
	static vector<float> sp(v.size()+1);
	partial_sum(begin(v), end(v), begin(sp)+1);
	deque<short> d;
	for(int i = l; i <= v.size(); ++i){
		while((!d.empty()) && sp[d.front()] > sp[i-l]){
			d.pop_back(); }
		d.push_back(i-l);
		if(d.front() == i-(u+1)){
			d.pop_front(); }

		if(sp[i] - sp[d.front()] > 0){
			return true; } }
	return false; }

constexpr float epsilon = 1e-4;

bool e_zero(const float d){
	return -epsilon < d && d < epsilon; }

bool egal(const float a, const float b){
	return (a > b) ? egal(b, a) : a+epsilon >= b; }

double binary_search(const vector<short>& cost, const vector<short>& timp, const int l, const int u){
	const int max_v = accumulate(begin(cost), end(cost), 0);
	double jos = 0, sus = max_v, mij;
	vector<float> de_verificat(cost.size());
	while(!egal(jos, sus)){
		mij = jos + (sus-jos)/2;
		transform(begin(cost), end(cost), begin(timp), begin(de_verificat),
			[mij](const short c, const short t)->double{
				return c - mij*t; });
		if(exista_subsecv_pozitiva_de_lung_intre(de_verificat, l, u)){
			jos = mij; }
		else{
			sus = mij; } }
	return sus /* == jos */; }

int main(){
	ifstream f("secv3.in");
	ofstream g("secv3.out");
	int n, l, u;
	f >> n >> l >> u;
	vector<short> cost(n), timp(n);
	for(auto& x : cost){
		f >> x; }
	for(auto& x : timp){
		f >> x; }
	g << binary_search(cost, timp, l, u);
	return 0; }