oj.uz

Submission #237737

# Submission time Handle Problem Language Result Execution time Memory
237737 2020-06-08T14:21:12 Z Haunted_Cpp Feast (NOI19_feast) C++17
0 / 100
 67 ms 10864 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 3e5 + 5;

int arr [N];
vector<int> comp;
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<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;
    }
  }
  vector< vector<int> > g (N);
  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 <int> solve (vec); 
      res += solve.best;
    }
  }
  cout << res << '\n';
  return 0;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 1912 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 8704 KB Output is correct
2 Correct 32 ms 8568 KB Output is correct
3 Correct 32 ms 8568 KB Output is correct
4 Correct 37 ms 1532 KB Output is correct
5 Incorrect 61 ms 9460 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 67 ms 10864 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 7424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 7424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 7424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 1912 KB Output isn't correct
2 Halted 0 ms 0 KB -