Submission #975931

#	Time	Username	Problem	Language	Result	Execution time	Memory
975931		vjudge1	Feast (NOI19_feast)	C++17	0 / 100	1051 ms	6956 KiB

feast

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

using namespace std;

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

    int N, K;
    cin >> N >> K;

    vector<int> A(N);
    vector<int> prefixSum(N + 1, 0);

    // Read satisfaction points and compute prefix sums
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        prefixSum[i + 1] = prefixSum[i] + A[i];
    }

    // Define a dynamic programming array
    vector<int> dp(N + 1);

    // Iterate over the number of people
    for (int j = 1; j <= K; ++j) {
        // Initialize binary search parameters
        int left = 0, right = N;

        // Binary search to find the optimal partition for each person
        while (left < right) {
            int mid = (left + right + 1) / 2;

            // Calculate the maximum satisfaction points achievable for the current segment
            int maxSum = prefixSum[mid];
            for (int i = 1; i <= mid; ++i) {
                maxSum = max(maxSum, prefixSum[mid] - prefixSum[i]);
            }

            // Check if the current segment satisfies the condition
            if (maxSum > dp[mid]) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }

        // Update dynamic programming table
        for (int i = 0; i <= N; ++i) {
            dp[i] = max(dp[i], prefixSum[left] - prefixSum[i]);
        }
    }

    cout << dp[N] << endl;

    return 0;
}

• 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