Submission #1145428

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145428		amsah	Feast (NOI19_feast)	C++20	100 / 100	107 ms	12172 KiB

feast

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define int ll
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

void dbg_out() { cerr << endl; }
template <typename H, typename... T>
void dbg_out(H h, T... t) { cerr << ' ' << h; dbg_out(t...); }
#define dbg(...) { cerr << #__VA_ARGS__ << ':'; dbg_out(__VA_ARGS__); }

const int INF = 1e15;
const int N = 3e5;

pair<int, int> dp[N][2];

int solve() {
  int n, k; cin >> n >> k;
  vector<int> a(n);
  for (int i = 0; i < n; i++) cin>>a[i];

  // I want (at most) K segments.
  // Positive values I always want to take the most.
  auto eval = [&](int lambda) {
    // Lambda is the penalty.
    // Creating a new segment costs lambda.
  
    // dp[i][0] := Best sum not using i.
    // dp[i][1] := Best sum using i.
    dp[0][0] = {0, 0};
    dp[0][1] = {a[0]-lambda, 1};
    for (int i = 1; i < n; i++) {
      dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
      dp[i][1] = max<pair<int, int>>(
        {dp[i-1][0].first + a[i] - lambda, dp[i-1][0].second + 1},
        {dp[i-1][1].first + a[i], dp[i-1][1].second}
      );
    }
    return max(dp[n-1][0], dp[n-1][1]);
  };

  // eval(0) will use a segment for each positive value.
  // eval(INF) will never create a segment.
  int lo = 0, hi = INF;
  while (hi-lo > 1) {
    int mid = (lo + hi)/2;
    auto [cost, used] = eval(mid);
    if (used >= k) lo = mid;
    else hi = mid;
  }
  auto [res, _] = eval(lo);
  return res + k*lo;
}

signed main() {
	cin.tie(0)->sync_with_stdio(false);
	cin.exceptions(cin.failbit);
  cout << solve() << '\n';
	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