CF 579 Div. 3 F Complete the Projects

Problem - F2 - Codeforces

I wonder why my solutions passes. My solution is quite different from the official solution. We assume that the optimal solution forms like this. In the following figure, elements are sorted in descending order according to a[i].

 +-------+     +-----+     +---------+
 v       |     v     |     v         |
+-+-+-+-+-+   +-+-+-+-+   +-+-+-+-+-+-+
|5|1|2|3|4|   |4|1|2|3|   |6|1|2|3|4|5|
+-+-+-+-+-+   +-+-+-+-+   +-+-+-+-+-+-+
 |             | ^         | ^
 +---------------+         +-|------------ ...
               +-------------+

If this is right, we can solve this problem by the following algorithm. If you find any hack case, you can hack it from https://codeforces.com/contest/1203/submission/58747572.

#include <bits/stdc++.h>
 
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
 
using namespace std;
using ll = long long;
 
void chmax(int &x, int y) {
  x = max(x, y);
}
 
int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int n, r; cin >> n >> r;
  vector<int> a(n), b(n);
  vector<int> pos, neg;
  rep(i, n) {
    cin >> a[i] >> b[i];
    if (b[i] >= 0) pos.push_back(i);
    else neg.push_back(i);
  }
  sort(pos.begin(), pos.end(), [&](int i, int j) {
    return a[i] < a[j];
  });
  sort(neg.begin(), neg.end(), [&](int i, int j) {
    return a[i] > a[j];
  });
  int cnt = 0;
  for (int i : pos) {
    if (r < a[i]) continue;
    r += b[i];
    cnt++;
  }
  static int dp[101][102][102];
  rep(i, 101) rep(j, 102) rep(k, 102) dp[i][j][k] = -1e9;
  const int m = neg.size();
  dp[0][m][0] = r;
  for (int i = 0; i <= m; i++) {
    for (int j = 0; j <= m; j++) {
      for (int k = 0; k <= m; k++) {
        if (j != m) {
          if (dp[i][j][k] >= a[neg[j]]) {
            chmax(dp[i][m][k+1], dp[i][j][k] + b[neg[j]]);
          }
        }
        if (i < m) {
          chmax(dp[i+1][j][k], dp[i][j][k]);
          if (dp[i][j][k] >= a[neg[i]]) {
            chmax(dp[i+1][j][k+1], dp[i][j][k] + b[neg[i]]);
          }
        }
        if (i < m && j == m) {
          chmax(dp[i+1][i][k], dp[i][j][k]);
        }
      }
    }
  }
  repr(i, m+1) {
    if (dp[m][m][i] >= 0) {
      cout << i + cnt << endl;
      return 0;
    }
  }
}