#include // 準備: pair の和、スカラー倍 template std::pair operator+(const std::pair& lhs, const std::pair& rhs) { return {lhs.first + rhs.first, lhs.second + rhs.second}; } template std::pair operator*(const S& lhs, const std::pair& rhs) { return {lhs * rhs.first, lhs * rhs.second}; } // Stern-Brocot Tree の探索 // judge_function(a, b) は非負有理数から {true, false} への写像であって、 // ある分子・分母ともに max_value 以下であるような有理数 x/y によって a/b と x/y の大小関係で true, false が定まるもの。 // x/y を O(log max_value) 時間で求める。 template std::pair stern_brocot_tree_search(Judge&& judge_function, const Integer& max_value) { std::pair lower{0, 1}, upper{1, 0}, now{1, 1}; // 下界 0/1 上界 1/0 while (true) { now = lower + upper; const auto now_judge{judge_function(now)}; auto &from{now_judge ? lower : upper}, &to{now_judge ? upper : lower}; // from から to へ向かって潜っていく // 指数探索 // 1. 上限を探索 Integer L{1}, R{2}; while (judge_function(from + R * to) == now_judge) { L *= 2; R *= 2; // max_value より下まで潜ったら、それ以降無限に潜る -> 答えは to (= from + ∞ * to) if ((from + L * to).first > max_value || (from + L * to).second > max_value)return to; } // 2. 二分探索 while (L + 1 < R) { const auto M{(L + R) / 2}; (judge_function(from + M * to) == now_judge ? L : R) = M; } from = from + L * to; } } #include #include int main() { using namespace std; using bigint = boost::multiprecision::cpp_int; using bigrat = boost::rational; unsigned N; cin >> N; vector A(N), B(N); for (auto&& a : A) cin >> a; for (auto&& b : B) cin >> b; const auto& [num, den]{ stern_brocot_tree_search([N, &A, &B](const pair& x) { vector C(N); ranges::transform(A, B, begin(C), [&x](unsigned a, unsigned b) { return x.second * a - x.first * b; }); vector prefix_max(N), suffix_max(N); prefix_max.front() = C.front(); for (const auto i : views::iota(1U, N)) prefix_max[i] = max(prefix_max[i - 1], 0) + C[i]; for (const auto i : views::iota(0U, N - 1) | views::reverse) suffix_max[i] = max(suffix_max[i + 1] + C[i + 1], 0); return ranges::all_of(views::zip_transform(plus{}, prefix_max, suffix_max), [](const bigint& a){return a >= 0;}); }, max(ranges::fold_left(A, 0UL, plus{}), ranges::fold_left(B, 0UL, plus{})) + bigint{}) }; const auto rational_to_string{[](auto x, unsigned long dig = 100, bool round_up = false){ using rational_type = decltype(x); using integer_type = typename rational_type::int_type; const integer_type pow10{"1" + string(dig, '0')}; if(round_up && (x * pow10).numerator() % (x * pow10).denominator() != 0)x += rational_type{1, pow10}; integer_type num{x.numerator()}, den{x.denominator()}; string ret{}; if(num < 0){ ret += '-'; num *= -1; } ret += integer_type(num / den).str(); ret += "."; num %= den; for(unsigned long i{}; i < dig; ++i){ ret += integer_type((num *= 10) / den).str(); num %= den; } while(!empty(ret) && ret.back() == '0')ret.pop_back(); if(ret.back() == '.')ret.pop_back(); return ret; }}; const auto error_bound{[](auto x, unsigned long dig, bool is_upper = true, unsigned long coef = 1){ using rational_type = decltype(x); using integer_type = typename rational_type::int_type; const integer_type pow10{"1" + string(dig, '0')}; if(is_upper)return max({x + rational_type(coef, pow10), x * rational_type(pow10 + coef, pow10), x * rational_type(pow10 - coef, pow10)}); else return min({x - rational_type(coef, pow10), x * rational_type(pow10 + coef, pow10), x * rational_type(pow10 - coef, pow10)}); }}; cout << rational_to_string(error_bound(bigrat{num, den}, 6, false), 100, true) << endl; return 0; }