Submission #642043

#	Time	Username	Problem	Language	Result	Execution time	Memory
642043		valerikk	Candies (JOI18_candies)	C++17	8 / 100	5062 ms	26004 KiB

candies

#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>

using namespace std;

typedef long long ll;

const ll INF = 2e18;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  int n;
  cin >> n;

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

  vector dp(n + 1, vector<ll>(2, -INF));
  dp[0][0] = 0;
  for (int i = 0; i < n; ++i) {
    vector ndp(n + 1, vector<ll>(2, -INF));
    for (int j = 0; j <= n; ++j) {
      for (int f = 0; f < 2; ++f) {
        if (dp[j][f] == -INF) continue;
        for (int t = 0; t < 2 - f; ++t) {
          ndp[j + t][t] = max(ndp[j + t][t], dp[j][f] + a[i] * t);
        }
      }
    }
    dp = ndp;
  }

  vector<ll> ans((n + 1) / 2 + 1, -INF);
  for (int i = 0; i <= n; ++i) {
    if (dp[i][0] != -INF) {
      ans[i] = max(ans[i], dp[i][0]);
    }
    if (dp[i][1] != -INF) {
      ans[i] = max(ans[i], dp[i][1]);
    }
  }

  for (int i = 1; i < (n + 1) / 2; ++i) {
    assert(ans[i] - ans[i - 1] >= ans[i + 1] - ans[i]);
  }
  for (int i = 1; i <= (n + 1) / 2; ++i) {
    cout << ans[i] << "\n";
  }
  return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 0 / 92