#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{}) }; cout << setprecision(100) << static_cast(num) / static_cast(den) << endl; return 0; }