Submission #1229825

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229825		kawaii	Feast (NOI19_feast)	C++20	59 / 100	1096 ms	9800 KiB

feast

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

const long long INF = -1e18; // Use a sufficiently small negative number for initialization

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

    int n, k;
    cin >> n >> k;

    vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    // Compute prefix sums (0-based indexing for A, 1-based for prefix_sum)
    // prefix_sum[i] = sum of a[0]...a[i-1]
    vector<long long> prefix_sum(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        prefix_sum[i + 1] = prefix_sum[i] + a[i];
    }

    // dp[i] will store the maximum satisfaction using the first i plates (0..i-1)
    // with exactly j people (current iteration of j).
    vector<long long> prev_dp(n + 1, 0); // Base case: 0 people, max sat is 0 for any number of plates

    for (int j = 1; j <= k; ++j) {
        vector<long long> current_dp(n + 1, INF);
        current_dp[0] = 0; // 0 plates, j people assigned empty segments, max sat is 0.

        long long max_val = INF; // This will store max_{0 <= p < i} (prev_dp[p] - prefix_sum[p])

        for (int i = 1; i <= n; ++i) {
            // When computing current_dp[i] (using plates 0..i-1) for j people:
            // Option 1: j-th segment ends before plate i-1 (or is empty at i-1).
            // Max satisfaction is current_dp[i-1].
            current_dp[i] = current_dp[i - 1];

            // Option 2: j-th segment ends exactly at plate i-1.
            // It starts at some plate p (0 <= p <= i-1).
            // Sum = a[p] + ... + a[i-1] = prefix_sum[i] - prefix_sum[p].
            // Previous j-1 people used plates 0..p-1. Max sat is prev_dp[p].
            // Total = prev_dp[p] + prefix_sum[i] - prefix_sum[p].
            // We need max over 0 <= p <= i-1: max(prev_dp[p] - prefix_sum[p]) + prefix_sum[i].
            // The term max(prev_dp[p] - prefix_sum[p]) needs to be calculated for p up to i-1.
            // The required max_val for index i is max_{0 <= p <= i-1} (prev_dp[p] - prefix_sum[p]).
            // This can be updated iteratively: max_{0 <= p <= i-1} = max(max_{0 <= p <= i-2}, prev_dp[i-1] - prefix_sum[i-1])

            // Update max_val to include the term for index i-1: (prev_dp[i-1] - prefix_sum[i-1])
            // This max_val will be used for calculating current_dp[i], maximizing over segments ending at i-1.
            max_val = max(max_val, prev_dp[i-1] - prefix_sum[i-1]);

            // If max_val was not INF, we can potentially end the j-th segment at i-1
            if (max_val != INF) {
                 current_dp[i] = max(current_dp[i], max_val + prefix_sum[i]);
            }
        }
        prev_dp = current_dp;
    }

    cout << prev_dp[n] << endl;

    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