Submission #1131292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131292		Quan2003	Feast (NOI19_feast)	C++20	41 / 100	1096 ms	22484 KiB

feast

#include "bits/stdc++.h"

using namespace std;

#define sz(x) int(x.size())
#define mp make_pair

const int64_t oo = 1e16; 

int main(void) {
 ios_base::sync_with_stdio(false);
 cin.tie(0);
 cout.tie(0);
 int N, K; 
 cin >> N >> K; 
 vector<int>a(N + 1); 
 for(int i = 1; i <= N; i++) { 
  cin >> a[i]; 
 }
 auto check = [&](int64_t amt) { 
  vector<vector<pair<int64_t, int>>>dp(N + 1, vector<pair<int64_t, int>>(2, {-oo, 0})); 
  dp[0][0].first = 0; 
  for(int i = 1; i <= N; i++) { 
   dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]); 
   dp[i][1] = max(mp(dp[i - 1][0].first + a[i] - amt, dp[i - 1][0].second + 1), 
                  mp(dp[i - 1][1].first + a[i], dp[i - 1][1].second));
  }
  return max(dp[N][1], dp[N][0]); 
 }; 
 int64_t lo = 0, hi = oo; 
 while(lo < hi) { 
  int64_t mid = (lo + hi + 1) / 2; 
  check(mid).second >= K ? lo = mid : hi = mid - 1; 
 }
 auto [c, d] = check(lo); 
 cout << c + d * lo << '\n'; 
 return 0;
}

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