Submission #1295344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295344		blinky	Feast (NOI19_feast)	C++20	18 / 100	274 ms	12468 KiB

feast

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

using namespace std;
#define int long long 
int n, k;

// Returns {max_score, items_picked} for a given penalty lambda
pair<long long, int> check(vector<int> &a , long long lambda) {
    // dp[i] stores {score, count} for the prefix i
    vector<pair<long long, int>> dp0(n);
    vector<pair<long long, int>> dp1(n);


    // Base cases
    dp0[0] = {0,0}; // Pick first item
    dp1[0]={a[0]-lambda ,1};


    for (int i = 1; i < n; i++) {
        //dp0
  
      if( dp0[i-1].first>dp1[i-1].first){ 
        dp0[i] = dp0[i-1] ; 
      }else dp0[i] = dp1[i-1] ; 

      //dp1
      if ( dp1[i-1].first+a[i]< dp0[i-1].first+a[i]-lambda){ 
        dp1[i]= {dp0[i-1].first+a[i]-lambda, dp0[i-1].second+1} ;
      }
      else { 
        dp1[i].first=dp1[i-1].first +a[i]; 
        dp1[i].second=dp1[i-1].second;
      }
    }
    if (dp0[n-1].first > dp1[n-1].first )return dp0[n-1];


    return dp1[n - 1];
}

signed main() {
    // Example input

    long long low = INT_MIN, high = 1e15, ans_lambda = -1;
    
    // Binary Search     for Lambda
    cin >> n >> k ;
    vector<int> a(n);
    for ( auto &x: a)cin >> x ;  
    while (low <= high) {
        long long mid = low + (high - low) / 2;
        pair<long long, int> res = check(a,mid);
        
        if (res.second >= k) {
            ans_lambda = mid;
            low = mid + 1; // Try to increase penalty to reduce count
        } else {
            high = mid - 1;
        }
    }

    // Final Answer Reconstruction
    pair<long long, int> final_res = check(a, ans_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