Submission #1023161

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023161		avighna	Feast (NOI19_feast)	C++17	100 / 100	145 ms	15196 KiB

feast

#include <bits/stdc++.h>

typedef long long ll;

const ll N = 3e5 + 1;

std::pair<ll, ll> dp[N][2];

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    ll n, k;
    std::cin >> n >> k;
    std::vector<ll> a(n);
    for (auto &i : a) {
        std::cin >> i;
    }

    auto solve_dp = [&](ll p) {
        dp[0][0] = {0, 0};
        dp[0][1] = {a[0] - p, 1};
        for (ll i = 1; i < n; ++ i) {
            dp[i][1] = std::max(std::make_pair<ll, ll>(a[i] + dp[i - 1][1].first, ll(dp[i - 1][1].second)), std::make_pair<ll, ll>(a[i] + dp[i - 1][0].first - p, dp[i - 1][0].second + 1));
            dp[i][0] = std::max(dp[i - 1][0], dp[i - 1][1]);
        }
        dp[n][0] = std::max(dp[n - 1][0], dp[n - 1][1]);
        return dp[n][0];
    };

    ll lo = 0, hi = 1e18;
    for (ll i = 0; i < 64; ++ i) {
        ll p = (lo + hi) / 2;
        if (solve_dp(p).second <= k) {
            hi = p;
        } else {
            lo = p;
        }
    }
    auto dp = solve_dp(hi);
    std::cout << dp.first + dp.second * hi << "\n";
}

• 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