Submission #226591

#	Time	Username	Problem	Language	Result	Execution time	Memory
226591		bortoz	Feast (NOI19_feast)	C++17	12 / 100	117 ms	27112 KiB

feast

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define pc __builtin_popcount

constexpr int MAXN = 1 << 17;

int main() {
  ios::sync_with_stdio(false);

  int N, K;
  cin >> N >> K;

  map<int, ll> S;
  ll sum = 0;
  for (int i = 0; i < N; i++) {
    int a;
    cin >> a;
    if (a == 0 || (sum == 0 && a < 0)) continue;
    if ((a >= 0) == (sum >= 0)) {
      sum += a;
    } else {
      S.emplace(i, sum);
      sum = a;
    }
  }
  if (sum > 0) S.emplace(N, sum);

  priority_queue<pair<ll, int>> Q;
  for (auto [i, x] : S) {
    Q.emplace(-abs(x), i);
  }

  while (S.size() > 2 * K) {
    auto [_, i] = Q.top();
    Q.pop();
    auto it = S.find(i);
    if (it == S.begin()) {
      S.erase(next(it));
      S.erase(it);
    } else if (next(it) == S.end()) {
      S.erase(prev(it));
      S.erase(it);
    } else {
      auto pv = prev(it), nx = next(it);
      it->se += pv->se + nx->se;
      S.erase(pv);
      S.erase(nx);
      Q.emplace(-abs(it->se), it->fi);
    }
  }

  ll res = 0;
  for (auto [_, x] : S) {
    res += max(x, 0ll);
  }
  cout << res << endl;

  return 0;
}

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:36:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (S.size() > 2 * K) {
          ~~~~~~~~~^~~~~~~
feast.cpp:37:15: warning: unused variable '_' [-Wunused-variable]
     auto [_, i] = Q.top();
               ^
feast.cpp:56:18: warning: unused variable '_' [-Wunused-variable]
   for (auto [_, x] : S) {
                  ^

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