Pagini recente » Cod sursa (job #966977) | Cod sursa (job #2586128) | Cod sursa (job #1877483) | Cod sursa (job #3239296) | Cod sursa (job #1472887)
#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-4;
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; }