제출 #237739

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
237739		Haunted_Cpp	Feast (NOI19_feast)	C++17	30 / 100	72 ms	14444 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 (const vector<T> &a) {
    best = cur = s = start = end = 0LL;
    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 = 0;
  for (int i = 0; i < (int) comp.size() ; i++) if (comp[i] > 0) ++tot;
  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<int> 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;
    }
  }
  assert (blocos == k);
  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: 8 / 8
• Subtask 3: 18 / 18
• Subtask 4: 0 / 10
• Subtask 5: 0 / 11
• Subtask 6: 0 / 20
• Subtask 7: 0 / 29