Submission #1229881

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229881		kawaii	Feast (NOI19_feast)	C++20	30 / 100	90 ms	8604 KiB

feast

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

using namespace std;

const long long INF = -3e18; // Needs to be smaller than any possible penalized value

struct Result {
    long long value;
    int count;

    // For lexicographical comparison (maximize value, then minimize count)
    bool operator<(const Result& other) const {
        if (value != other.value) {
            return value < other.value;
        }
        return count > other.count; // Minimize count for ties
    }
};

// O(N) DP function for the modified problem with penalty C
Result solve_modified(int n, int k, const vector<long long>& a, const vector<long long>& prefix_sum, long long C) {
    vector<long long> dp(n + 1, INF);
    vector<int> count(n + 1, 0);
    dp[0] = 0; // 0 plates, 0 segments, 0 penalized value

    // best_prev_state stores (dp[k] - prefix_sum[k], count[k]) for k < i
    // Used to calculate max_{0 <= k <= i-1} (dp[k] - prefix_sum[k])
    Result best_prev_state = {0LL, 0}; // Represents dp[0] - prefix_sum[0]

    for (int i = 1; i <= n; ++i) {
        // Option 1: Plate i is not the end of a segment.
        // Use result from dp[i-1], count[i-1].
        // We initialize dp[i], count[i] with this implicitly in the loop structure,
        // but let's be explicit for clarity in the max comparison.
        Result option1 = {dp[i-1], count[i-1]};

        // Option 2: Plate i is the end of a segment.
        // Value = max_{0 <= k <= i-1} (dp[k] - prefix_sum[k]) + prefix_sum[i] - C
        // Count = count for max_{0 <= k <= i-1} (dp[k] - prefix_sum[k]) + 1
        Result option2 = {INF, 0}; // Default in case best_prev_state is INF (shouldn't happen with dp[0]=0)
        if (best_prev_state.value != INF) { // Check if best_prev_state is valid
             option2.value = best_prev_state.value + prefix_sum[i] - C;
             option2.count = best_prev_state.count + 1;
        }


        // Choose the better result for dp[i], count[i]
        if (option2.value > option1.value) {
            dp[i] = option2.value;
            count[i] = option2.count;
        } else if (option1.value > option2.value) {
             dp[i] = option1.value;
             count[i] = option1.count;
        } else { // option1.value == option2.value
             dp[i] = option1.value;
             count[i] = min(option1.count, option2.count); // Minimize count on tie
        }

        // Update best_prev_state for the next iteration (i+1)
        // It needs to include the state from dp[i]
        Result current_state_contribution = {dp[i] - prefix_sum[i], count[i]};

        // Update best_prev_state if current_state_contribution is better
        if (current_state_contribution < best_prev_state) { // Using the overloaded < operator
             // best_prev_state is already better or equal with lower count
        } else {
             best_prev_state = current_state_contribution;
        }
        if (count[i] >= k){
          return {0, k};
        }
    }

    return {dp[n], count[n]};
}

Result real_solve_modified(int n, int k, const vector<long long>& a, const vector<long long>& prefix_sum, long long C) {
    vector<long long> dp(n + 1, INF);
    vector<int> count(n + 1, 0);
    dp[0] = 0; // 0 plates, 0 segments, 0 penalized value

    // best_prev_state stores (dp[k] - prefix_sum[k], count[k]) for k < i
    // Used to calculate max_{0 <= k <= i-1} (dp[k] - prefix_sum[k])
    Result best_prev_state = {0LL, 0}; // Represents dp[0] - prefix_sum[0]

    for (int i = 1; i <= n; ++i) {
        // Option 1: Plate i is not the end of a segment.
        // Use result from dp[i-1], count[i-1].
        // We initialize dp[i], count[i] with this implicitly in the loop structure,
        // but let's be explicit for clarity in the max comparison.
        Result option1 = {dp[i-1], count[i-1]};

        // Option 2: Plate i is the end of a segment.
        // Value = max_{0 <= k <= i-1} (dp[k] - prefix_sum[k]) + prefix_sum[i] - C
        // Count = count for max_{0 <= k <= i-1} (dp[k] - prefix_sum[k]) + 1
        Result option2 = {INF, 0}; // Default in case best_prev_state is INF (shouldn't happen with dp[0]=0)
        if (best_prev_state.value != INF) { // Check if best_prev_state is valid
             option2.value = best_prev_state.value + prefix_sum[i] - C;
             option2.count = best_prev_state.count + 1;
        }


        // Choose the better result for dp[i], count[i]
        if (option2.value > option1.value) {
            dp[i] = option2.value;
            count[i] = option2.count;
        } else if (option1.value > option2.value) {
             dp[i] = option1.value;
             count[i] = option1.count;
        } else { // option1.value == option2.value
             dp[i] = option1.value;
             count[i] = min(option1.count, option2.count); // Minimize count on tie
        }

        // Update best_prev_state for the next iteration (i+1)
        // It needs to include the state from dp[i]
        Result current_state_contribution = {dp[i] - prefix_sum[i], count[i]};

        // Update best_prev_state if current_state_contribution is better
        if (current_state_contribution < best_prev_state) { // Using the overloaded < operator
             // best_prev_state is already better or equal with lower count
        } else {
             best_prev_state = current_state_contribution;
        }
    }

    return {dp[n], count[n]};
}

// Main binary search logic
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];
    }

    vector<long long> prefix_sum(n + 1, 0);
    long long mx = 0, mn_sum = 0;
    for (int i = 0; i < n; ++i) {
        prefix_sum[i + 1] = prefix_sum[i] + a[i];
        mn_sum = min(mn_sum, prefix_sum[i + 1]);
        mx = max(mx, prefix_sum[i + 1] - mn_sum);
    }

    // Binary search for penalty C
    long long low = -1e9 - 1, high = 1e18; // Sufficiently wide range for penalty
    Result final_result = {INF, 0}; // Store the best result found where count >= K

    for(int iter = 0; iter < 100; ++iter) { // Fixed iterations for precision
        long long mid = low + (high - low) / 2;
        Result current_res = solve_modified(n, k, a, prefix_sum, mid);

        if (current_res.count >= k) {
            // Penalty is too low or just right. Store this as a potential answer.
            // Try higher penalty to get closer to K or potentially a slightly better value at >= K.
            low = mid;
        } else {
            // Penalty is too high, got less than K segments. Need lower penalty.
            high = mid;
        }
    }

    // The final_result contains (penalized_value, count) from the DP run
    // with the optimal penalty C_opt (which is 'low' or 'high' after binary search).
    // We need the true max satisfaction for EXACTLY K segments.
    // MaxSat(K) = PenalizedValue + C_opt * K
    // Since final_result was obtained with penalty 'low' (the C_opt),
    // MaxSat(final_result.count) = final_result.value + low * final_result.count.
    // The answer for K segments is:
    final_result = real_solve_modified(n, k, a, prefix_sum, low);
    long long max_satisfaction_k = final_result.value + low * final_result.count;

    cout << max_satisfaction_k << endl;

    return 0;
}

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