Submission #1101997

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101997		Zero_OP	Feast (NOI19_feast)	C++14	100 / 100	128 ms	13920 KiB

feast

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int MAX = 3e5 + 5;
pair<ll, int> dp[2][MAX];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    if(fopen("task.inp", "r")){
        freopen("task.inp", "r", stdin);
        freopen("task.out", "w", stdout);
    }


    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
    }

    auto f = [&](ll lambda) -> pair<ll, int> {
        dp[0][1] = {0, 0};
        dp[1][1] = {a[1] - lambda, 1};
        for(int i = 2; i <= n; ++i){
            dp[0][i] = max(dp[0][i - 1], dp[1][i - 1]);
            dp[1][i] = max(make_pair(dp[0][i - 1].first + a[i] - lambda, dp[0][i - 1].second + 1),
                           make_pair(dp[1][i - 1].first + a[i], dp[1][i - 1].second));
        }

        return max(dp[0][n], dp[1][n]);
    };

    ll l = 0, r = 1e18, lambda_opt = 0;
    while(l <= r){
        ll mid = l + r >> 1;
        pair<ll, int> eval = f(mid);
        if(eval.second >= k) lambda_opt = mid, l = mid + 1;
        else r = mid - 1;
    }

    ll ret = f(lambda_opt).first + lambda_opt * k;
    cout << ret << '\n';

    return 0;
}

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:41:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |         ll mid = l + r >> 1;
      |                  ~~^~~
feast.cpp:15:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |         freopen("task.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
feast.cpp:16:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         freopen("task.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• 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