Submission #1263407

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263407		baodat	Feast (NOI19_feast)	C++20	59 / 100	161 ms	327680 KiB

feast

#include <bits/stdc++.h>
using namespace std;

using int64 = long long;
const int64 NINF = (int64)-4e18;

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

    int n, k;
    if (!(cin >> n >> k)) return 0;

    vector<int64> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    // dp_in[i][t]: best sum using first i, started exactly t segments, currently inside
    // dp_out[i][t]: ... currently outside
    vector<vector<int64>> dp_in(n + 1, vector<int64>(k + 1, NINF));
    vector<vector<int64>> dp_out(n + 1, vector<int64>(k + 1, NINF));
    dp_out[0][0] = 0;

    for (int i = 1; i <= n; ++i) {
        for (int t = 0; t <= k; ++t) {
            // be outside at i: stay outside or close a segment
            dp_out[i][t] = max(dp_out[i - 1][t], dp_in[i - 1][t]);

            // be inside at i: extend, or start now (if we still can start)
            if (dp_in[i - 1][t] != NINF)
                dp_in[i][t] = max(dp_in[i][t], dp_in[i - 1][t] + a[i]);

            if (t > 0 && dp_out[i - 1][t - 1] != NINF)
                dp_in[i][t] = max(dp_in[i][t], dp_out[i - 1][t - 1] + a[i]);
        }
    }

    int64 ans = NINF;
    for (int t = 0; t <= k; ++t)
        ans = max(ans, max(dp_in[n][t], dp_out[n][t]));

    cout << ans << "\n";
    return 0;
}

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