Submission #933014

#	Time	Username	Problem	Language	Result	Execution time	Memory
933014		y_combinator	Feast (NOI19_feast)	C++17	100 / 100	104 ms	4556 KiB

feast

#include <algorithm>
#include <array>
#include <ios>
#include <iostream>
#include <utility>
#include <vector>

using State = std::pair<long long, int>;

auto solve() {

    auto k = 0;
    auto n = 0;

    std::cin >> n >> k;

    auto a = std::vector<int>(n);

    for (auto& x : a) {
        std::cin >> x;
    }

    auto lo = -1ll;
    auto mx_pts = 0ll;

    for (auto x : a) {
        mx_pts += std::max(x, 0);
    }

    const auto compute = [&](long long penalty) {
        auto dp = std::array<State, 2>();
        dp[1].first = -(mx_pts + 1);
        for (auto x : a) {
            const auto maximize = [](State& lhs, const State& rhs) {
                auto& [pts_l, cnt_l] = lhs;
                const auto& [pts_r, cnt_r] = rhs;
                if (pts_r > pts_l || (pts_r == pts_l && cnt_r < cnt_l)) {
                    lhs = rhs;
                }
            };
            auto new_dp = std::array<State, 2>();
            new_dp[0].first = -(mx_pts + 1);
            new_dp[1].first = -(mx_pts + 1);
            maximize(new_dp[0], dp[0]);
            maximize(new_dp[0], State({dp[0].first + x - penalty, dp[0].second + 1}));
            maximize(new_dp[1], State({dp[0].first + x, dp[0].second}));
            maximize(new_dp[0], State({dp[1].first + x - penalty, dp[1].second + 1}));
            maximize(new_dp[1], State({dp[1].first + x, dp[1].second}));
            dp = std::move(new_dp);
        }
        return dp;
    };
    auto hi = mx_pts + 1;

    while (hi - lo > 1) {
        const auto mid = (lo + hi) >> 1;
        (compute(mid)[0].second < k ? hi : lo) = mid;
    }

    const auto [pts, cnt] = std::move(compute(lo)[0]);

    std::cout << pts + lo * cnt << '\n';

}

auto main() -> int {

    std::cin.tie(nullptr);

    std::ios_base::sync_with_stdio(false);

    solve();

    return 0;

}

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11
• Subtask 6: 20 / 20
• Subtask 7: 29 / 29