Submission #1308976

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308976		lyra_g13	Feast (NOI19_feast)	C++20	0 / 100	174 ms	327680 KiB

feast

#include <bits/stdc++.h>
using ll = long long;
using namespace std;

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

  ll n, k;
  cin >> n >> k;

  vector<ll> a(n);

  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }

  vector<vector<ll>> dp(n, vector<ll>(k + 1));

  vector<ll> pref(n);
  vector<ll> minpref(n);
  pref[0] = a[0];
  for (int i = 1; i < n; i++) {
    pref[i] = pref[i - 1] + a[i];
    if (pref[i] < pref[i - 1]) {
      minpref[i] = i;
    } else {
      minpref[i] = minpref[i - 1];
    }
  }

  ll maxval = 0;
  for (int i = 0; i < n; i++) {
    ll sum = pref[i] - minpref[i];
    if (sum > maxval) {
      maxval = sum;
    }
    dp[i][1] = maxval;
  }

  for (int i = 0; i < k; i++) {
    if (a[0] > 0) {
      dp[0][i] = a[i];
    } else
      dp[0][i] = 0;
  }

  for (int i = 1; i < n; i++) {
    for (int j = 2; j <= k; j++) {

      ll up = dp[i][j];

      up = max(up, dp[i - 1][j]);
      up = max(up, dp[i][j - 1]);
      up = max(up, dp[i][j - 1] + a[i]);

      ll add = minpref[i];
      ll addval = dp[add][j - 1];

      up = max(up, addval + dp[i][j - 1]);

      dp[i][j] = up;
    }
  }

  cout << dp[n - 1][k];
}

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