Submission #1142842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142842		AverageAmogusEnjoyer	Feast (NOI19_feast)	C++20	100 / 100	113 ms	10824 KiB

feast

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; }

mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> ui(0, 1 << 30);

int rng() { 
  return ui(mrand);
}

int main() {
  ios_base::sync_with_stdio(false); 
  cin.tie(nullptr);

  int n,k;
  cin >> n >> k;
  vector<int> v(n);
  for (int &x: v)
    cin >> x;
  vector<array<pair<ll,ll>,2>> dp(n);
  auto solve = [&](ll pen) {
    dp[0][1] = {v[0] - pen,1};
    dp[0][0] = {0,0};
    for (int i=1;i<n;i++) {
      dp[i][1] = max<pair<ll,ll>>({dp[i-1][1].first + v[i],dp[i-1][1].second},
                      {dp[i-1][0].first + v[i] - pen,dp[i-1][0].second + 1});
      dp[i][0] = max(dp[i-1][0],dp[i-1][1]);
    }
    return max(dp[n-1][0],dp[n-1][1]);
  };
  ll lo = 0, hi = 1LL << 60;
  while(lo < hi) {
    ll mid = lo + (hi - lo + 1) / 2;
    if (solve(mid).second >= k)
      lo = mid;
    else
      hi = mid - 1;
  }    
  cout << solve(lo).first + lo * k << "\n";
}

• 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