oj.uz

Submission #975936

# Submission time Handle Problem Language Result Execution time Memory
975936 2024-05-06T03:38:33 Z vjudge1 Feast (NOI19_feast) C++17
0 / 100
 1000 ms 4052 KB 
#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) / 2;

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

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

        // 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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1040 ms 3672 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 4052 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 3932 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1040 ms 3672 KB Time limit exceeded
2 Halted 0 ms 0 KB -