Submission #237738

#	Time	Username	Problem	Language	Result	Execution time	Memory
237738		Haunted_Cpp	Feast (NOI19_feast)	C++17	22 / 100	74 ms	15980 KiB

feast

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

const int N = 3e5 + 5;

vector<long long> arr (N);
vector<long long> comp;
vector< vector<long long> > g (N);
bool is_rem [N];

template<typename T>
struct Kadane {
  long long best;
  long long cur;
  int s, start, end;
  Kadane (vector<T> &a) {
    best = cur = s = start = end = 0;
    for (int i = 0; i < (int) a.size(); i++) {
      cur += a[i];
      if (cur < 0) {
        cur = 0;
        s = i + 1;
      }
      if (cur > best) {
        best = cur;
        start = s;
        end = i + 1;
      }
    }
  }
};

int main () {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  for (int i = 0; i < n; i++) cin >> arr[i];
  for (int i = 0; i < n; i++) {
    if (comp.empty() || ( (arr[i] >= 0)  ^ (comp.back() >= 0) ) == true ) {
      comp.emplace_back(arr[i]);
      continue;
    }
    long long cur = arr[i];
    while (!comp.empty() && ( (arr[i] >= 0)  ^ (comp.back() >= 0) ) == false ) {
      cur += comp.back();
      comp.pop_back();
    }
    comp.emplace_back(cur);
  }
  int tot = count_if (comp.begin(), comp.end(), [&] (int x) {
    return (x > 0);
  });
  if (tot <= k) {
    long long s = 0;
    for (auto to : comp) s += (to >= 0 ? to : 0);
    cout << s << '\n';
    return 0;
  }
  int primeiro = -1;
  int ultimo = -1;
  for (int i = 0; i < (int) comp.size(); i++) {
    if (comp[i] > 0) {
      if (primeiro == -1) primeiro = i;
      else ultimo = i + 1;
    }
  }
  vector<long long> neg;
  for (int i = primeiro; i < ultimo; i++) {
    if (comp[i] < 0) {
      neg.emplace_back(i);
    }
  }
  sort (neg.begin(), neg.end(), [&] (int x, int y) {
    return comp[x] < comp[y];
  });
  int blocos = 1;
  for (auto to : neg) {
    if (blocos < k) {
      ++blocos;
      is_rem[to] = true;
    }
  }
  int idx = 0;
  for (int i = primeiro; i < ultimo; i++) {
    if (is_rem[i]) {
      ++idx;
      continue;
    }
    g[idx].emplace_back(comp[i]);
  }
  long long res = 0;
  for (auto vec : g) {
    if (!vec.empty()) {
      Kadane <long long> solve (vec); 
      res += solve.best;
    }
  }
  cout << res << '\n';
  return 0;
}

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