paoPaoPkg.cc

#include <vector>
#include <cassert>

using namespace std;

class Solver {
public:
  Solver() = default;
  int solve(vector<int>& pkgs) {
    if (pkgs.empty()) return 0;

    int n = pkgs.size();
    int curMax = pkgs[n - 1];
    for (int i = n - 2; i >= 0; i--) {
      if (pkgs[i] >= curMax) {
        curMax = pkgs[i];
      } else {
        curMax += pkgs[i];
      }
    }
    return curMax;
  }
};

void tests() {
  {
    Solver s;
    vector<int> pkgs = {2, 9, 10, 3, 7};
    assert(s.solve(pkgs) == 21);
  }

  {
    Solver s;
    vector<int> pkgs = {2, 9, 11, 3, 7};
    assert(s.solve(pkgs) == 22);
  }

  {
    Solver s;
    vector<int> pkgs = {2, 3, 7};
    assert(s.solve(pkgs) == 12);
  }
}

int main() {
  tests();
  return 1;
}