Cod sursa(job #1472885)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 17 august 2015 23:13:23
Problema Secventa 3 Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 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<double>& v, const int l, const int u){
	static vector<double> sp(v.size()+1);
	partial_sum(begin(v), end(v), begin(sp)+1);
	deque<int> 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 double epsilon = 1e-2;

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

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

double binary_search(const vector<int>& cost, const vector<int>& 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<double> 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 int c, const int 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<int> 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; }