Submission #996992

#	Time	Username	Problem	Language	Result	Execution time	Memory
996992		blackslex	Feast (NOI19_feast)	C++17	100 / 100	113 ms	11612 KiB

feast

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<ll, ll>;

int n, k;

int main() {
    scanf("%d %d", &n, &k);
    vector<ll> a(n + 5), pref(n + 5);
    vector<pii> dp(n + 5);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]), pref[i] = pref[i - 1] + a[i];
    auto get = [&] (ll x) {
        pii cmx(0, 0);
        for (int i = 1; i <= n; i++) {
            dp[i] = max(dp[i - 1], {cmx.first + pref[i] - x, cmx.second - 1});
            cmx = max(cmx, {dp[i].first - pref[i], dp[i].second});
        }
        return pii(dp[n].first, -dp[n].second);
    };
    ll l = 0, r = 3e14;
    while (l <= r) {
        ll mid = (l + r) >> 1LL;
        if (get(mid).second <= k) r = mid - 1;
        else l = mid + 1;
    }
    printf("%lld", get(l).first + l * k);
}

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
feast.cpp:13:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     for (int i = 1; i <= n; i++) scanf("%lld", &a[i]), pref[i] = pref[i - 1] + a[i];
      |                                  ~~~~~^~~~~~~~~~~~~~~

• 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