Source Code
#include <bits/stdc++.h>

using namespace std;

const int N = 1003;

//                D   U  R  L
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};

int mem[6][N][N];

vector<string> g;

int n, m;

int main() {
  int n;
  cin >> n;
  vector<long long> v(n);
  vector<long long> arr;
  for (auto &a : v) cin >> a;
  int fn = -1;
  for (int i = 0; i < n; i++) {
    if (v[i] < 0) {
      if (fn == -1) {
        fn = arr.size();
        arr.push_back(v[i]);
      } else {
        arr[fn] += v[i];
      }
    } else {
      arr.push_back(v[i]);
    }
  }
  n = arr.size();
  vector<int> mid(n, n);
  long long mn = 2e18;
  int li = n;
  for (int i = n - 1; i >= 0; i--) {
    if (arr[i] < mn) {
      mn = arr[i];
      li = i;
    }
    mid[i] = li;
  }
  // for (int i = 0; i < n; i++) {
  //   cout << mid[i] << ' ';
  // }
  // cout << endl;
  int at = 0;
  vector<bool> was(n, true);
  while (at < n) {
    int nxt_min = mid[at];
    for (int i = at; i < nxt_min; i++) {
      if (arr[i] > 0) {
        arr[n - 1] += arr[i];
        was[i] = false;
      }
    }
    at = nxt_min + 1;
  }

  // int first = -1;
  // int neg = -1;
  // for (int i = 0; i < n; i++) {
  //   if (was[i]) {
  //     if(first == -1) {
  //       first = i;
  //       neg =
  //     }
  //   }
  // }
  int last = n - 1;
  while (last > 0 && was[last] && arr[last] == 0) {
    --last;
  }
  for (int i = 0; i <= last; i++) {
    if (was[i]) cout << arr[i] << ' ';
  }
  cout << endl;
}
Copy
a MaxHeap
GNU G++17
0 ms
496 KB
Wrong Answer