Submission #1295350

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295350		blinky	Feast (NOI19_feast)	C++20	100 / 100	92 ms	10932 KiB

feast

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

using namespace std;

const long long INF = 1e18;
const int MAXN = 300005;

int n, k;
vector<int> a;

// Global DP arrays to prevent reallocation overhead (Speed optimization)
// storing {score, count}
pair<long long, int> dp0[MAXN]; // Gap state
pair<long long, int> dp1[MAXN]; // Active state

// Returns {max_score, items_picked} for a given penalty lambda
pair<long long, int> check(long long lambda) {
    // Base cases
    // dp0[0]: In a gap at index 0 (didn't pick a[0])
    dp0[0] = {0, 0};
    
    // dp1[0]: Active at index 0 (Must have started a new segment)
    // Note: We pay the lambda cost immediately upon starting
    dp1[0] = {a[0] - lambda, 1};

    for (int i = 1; i < n; i++) {
        // --- 1. Calculate DP0 (Gap State) ---
        // We are NOT eating a[i]. Came from Gap(i-1) or Active(i-1).
        // If scores are equal, we usually prefer fewer segments to be safe,
        // but standard max logic works fine here.
        if (dp0[i-1].first >= dp1[i-1].first) {
            dp0[i] = dp0[i-1];
        } else {
            dp0[i] = dp1[i-1];
        }

        // --- 2. Calculate DP1 (Active State) ---
        // We ARE eating a[i].
        
        // Option A: Extend current segment (Free, just add a[i])
        long long extend_score = dp1[i-1].first + a[i];
        int extend_cnt = dp1[i-1].second;

        // Option B: 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;

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

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

int main() {
    // Optimization for faster I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if (!(cin >> n >> k)) return 0;
    
    a.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // Binary Search Range
    // Low must be 0 (At most K logic).
    // High is roughly max possible sum (3e14), 1e15 is safe.
    long long low = 0, high = 1e15;
    long long ans_lambda = 0;

    while (low <= high) {
        long long mid = low + (high - low) / 2;
        pair<long long, int> res = check(mid);

        // If we pick >= K segments, the penalty is too cheap (or just right).
        // We want the largest penalty that still gives us >= K segments 
        // (closest to touching the curve at K).
        if (res.second >= k) {
            ans_lambda = mid;
            low = mid + 1; // Try to increase penalty
        } else {
            high = mid - 1;
        }
    }

    // Final Reconstruction
    pair<long long, int> final_res = check(ans_lambda);
    
    // If the best lambda (0) still gave us < K segments, it means
    // it's optimal to pick fewer than K. The rest are empty segments (sum 0).
    // In that case, the formula adds 0 * K, which is correct.
    // However, if we forced it with a positive lambda, we add back K * lambda.
    
    long long answer = final_res.first + (long long)k * ans_lambda;
    cout << answer << endl;

    return 0;
}

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