Submission #917391

#	Time	Username	Problem	Language	Result	Execution time	Memory
917391		406	Feast (NOI19_feast)	C++17	100 / 100	112 ms	5876 KiB

feast

#include <bits/stdc++.h>
#define int long long
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)

using namespace std;
using ar = array<int, 2>;

const int64_t INF = 1ll << 60;
const int N = 3e5 + 5;
int n, k, a[N], ans;

bool check(const int O, bool f = 0) {
        ar dp{0, 0}, F{0, 0};
        int s = 0;
        FOR(i, 0, n) {
                s += a[i];
                F = max(F, ar{dp[0] - s, dp[1]});
                dp = max(dp, ar{s + F[0] - O, F[1] - 1});
        }
        if (f) ans = max(ans, dp[0] + k * O);
        return -dp[1] >= k;
}

signed main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr); 
        cin >> n >> k;
        FOR(i, 0, n) cin >> a[i];
        int l = 0, r = 1ll << 50;
        while (r - l > 1) {
                int m = l + r >> 1;
                if (check(m)) l = m;
                else r = m;
        }
        check(l, 1);
        cout << ans << '\n';
        return 0;
}

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:31:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |                 int m = l + r >> 1;
      |                         ~~^~~

• 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