Submission #1339176

#	Time	Username	Problem	Language	Result	Execution time	Memory
1339176		po_rag526	Feast (NOI19_feast)	C++20	0 / 100	1 ms	344 KiB

feast

// 2025/8/10: 911Lil_Marrikh - ECPC-2025 Medalists
#include <bits/stdc++.h>
using namespace std;

// #define int int64_t
#define ll int64_t
#define el "\n"

void work(int tc) {
    int n, k; cin >> n >> k;
    int a[n]; for (auto &i : a) cin >> i;

    auto solve = [&] (ll lmd) {
        pair<ll, int> dp[2][2];
        dp[0][0] = {0, 0};
        dp[0][1] = dp[1][0] = dp[1][1] = {-1e18, -1e9};
        for (int i = 0; i < n; i++) {
            dp[1][0] = max(dp[0][0], dp[0][1]);
            dp[1][1] = max<pair<ll, int>>(
                {dp[0][0].first + a[i] - lmd, dp[0][0].second + 1},
                {dp[0][1].first + a[i], dp[0][1].second}
            );
            swap(dp[0], dp[1]);
            dp[1][0] = dp[1][1] = {-1e18, -1e9};
        }
        return max(dp[0][0], dp[0][1]);
    };

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

    cout << solve(l).first + l * k;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int _t = 1;
    // cin >> _t;
    for (int i = 1; i <= _t; i++) {
        work(i);
    }
}

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:47:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
feast.cpp:48:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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