Submission #47270328

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/modint>

namespace {
using ModInt [[maybe_unused]] = atcoder::modint998244353;
using Num [[maybe_unused]] = long long int;
using Vec [[maybe_unused]] = std::vector<Num>;
using Set [[maybe_unused]] = std::set<Num>;
using Mset [[maybe_unused]] = std::multiset<Num>;
using Edges [[maybe_unused]] = std::vector<std::vector<Num>>;

template<typename T>
using Q [[maybe_unused]] = std::queue<T>;

template<typename T>
using PQ [[maybe_unused]] = std::priority_queue<T, std::vector<T>, std::greater<T>>;
}

void solve(std::istream& is, std::ostream& os) {
    Num n {0};
    is >> n;

    std::vector<double> ps(n);
    for(auto&& x : ps) {
        is >> x;
    }

    double answer {-1000000000000};
    for(Num i{0}; i<n; ++i) {
        const double r = ps.at(i) - 1200.0;
        if (i == 0) {
            answer = r;
        } else {
            answer = std::max(answer, r);
        }
    }

    std::vector<double> dp(n+1, -1000000000000);
    for(Num i{0}; i<n; ++i) {
        auto next = dp;
        const double r1 = ps.at(i) - 1200.0;
        next.at(1) = std::max(next.at(1), r1);
        answer = std::max(answer, next.at(1));

        for(Num j{2}; j<=n; ++j) {
            if ((i + 1) < j) {
                break;
            }

            double j1 = j - 1;
            double from = dp.at(j1);
            from += 1200 / std::sqrt(static_cast<double>(j1));
            from *= (1.0 - std::pow(0.9, j1)) / 0.1;
            from *= 0.9;
            from += ps.at(i);

            const double div = (1.0 - std::pow(0.9, j)) / 0.1;
            const double r = from / div - 1200 / sqrt(static_cast<double>(j));
            next.at(j) = std::max(next.at(j), r);
            answer = std::max(answer, next.at(j));
        }

        std::swap(dp, next);
    }

    os << std::setprecision(20) << answer << "\n";
}

int main(void) {
    solve(std::cin, std::cout);
    return 0;
}

Submission Info

Judge Result