Submission #1295347

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295347		blinky	Feast (NOI19_feast)	C++20	18 / 100	288 ms	11032 KiB

feast

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

using namespace std;

int n, k;
const long long INF = 1e18;

// Returns {max_score, items_picked} for a given penalty lambda
pair<long long, int> check(vector<int> &a , long long lambda) {
    vector<pair<long long, int>> dp0(n); // Gap state
    vector<pair<long long, int>> dp1(n); // Active state

    // --- FIX 1: Correct Base Cases ---
    // Gap at 0: We didn't eat a[0]. Score 0, Segments 0.
    dp0[0] = {0, 0}; 
    // Active at 0: We started a new segment at a[0].
    dp1[0] = {a[0] - lambda, 1};


    for (int i = 1; i < n; i++) {
        // --- DP0 (GAP) ---
        // We are NOT eating a[i]. We came from Gap(i-1) or Active(i-1).
        // If scores equal, prefer FEWER segments (min) or MORE (max)? 
        // Standard practice: just take max tuple (compares first, then second).
        if (dp0[i-1] >= dp1[i-1]) { 
            dp0[i] = dp0[i-1]; 
        } else {
            dp0[i] = dp1[i-1];
        }

        // --- DP1 (ACTIVE) ---
        // We ARE eating a[i].
        
        // Option 1: Extend existing segment (Free)
        // FIX 2: You MUST add a[i] to the score!
        long long extend_score = dp1[i-1].first + a[i];
        int extend_cnt = dp1[i-1].second;

        // Option 2: Start new segment (Pay Lambda)
        long long start_new_score = dp0[i-1].first + a[i] - lambda;
        int start_new_cnt = dp0[i-1].second + 1;

        // Compare
        if (start_new_score > extend_score) {
             dp1[i] = {start_new_score, start_new_cnt};
        } else {
             dp1[i] = {extend_score, extend_cnt};
        }
    }

    // Return the best of the two final states
    if (dp0[n-1].first > dp1[n-1].first) return dp0[n-1];
    return dp1[n-1];
}

int main() {
    cin >> n >> k;
    vector<int> a(n);
    for (auto &x : a) cin >> x;  

    // FIX 3: Allow negative lambda (bonus) for negative inputs
    long long low = -1e15, high = 1e15, ans_lambda = -1e18;
    
    while (low <= high) {
        long long mid = low + (high - low) / 2;
        pair<long long, int> res = check(a, mid);
        
        // If we have >= K segments, the penalty is too cheap (or just right).
        // We need to INCREASE penalty to reduce count, or store answer.
        if (res.second >= k) {
            ans_lambda = mid;
            low = mid + 1; 
        } else {
            high = mid - 1;
        }
    }

    pair<long long, int> final_res = check(a, ans_lambda);
    // Formula: Unconstrained_Score + (Target_K * Lambda)
    long long final_ans = final_res.first + (long long)k * ans_lambda;
    
    cout << final_ans << endl;
    
    return 0;
}

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