Problem: Example

Input

2 2 7
3 4
3 2
1 3
1 1
2 2
1 2
2 1
1 2
2 2
1 1


Output

5

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

int main() {
    int p, r, t;
    cin >> p >> r >> t;
    vector<int> l(r);
    vector<vector<int>> n(p, vector<int>(r));
    vector<int> P(t), R(t);
    for(int i = 0; i < r; ++i) {
        cin >> l[i];
    }
    for(int i = 0; i < p; ++i) {
        for(int j = 0; j < r; ++j) {
            cin >> n[i][j];
        }
    }
    for(int i = 0; i < t; ++i) {
        cin >> P[i] >> R[i];
        P[i]--; R[i]--;
    }

    int lb = 0, ub = t + 1;
    while(ub - lb > 1) {
        int m = (lb + ub) / 2;
        vector<int> available = l;
        vector<vector<pii>> need_r(r, vector<pii>(p));
        vector<vector<int>> used_r(p, vector<int>(r));
        vector<int> pos(r), cnt(p);
        queue<int> term_process;
        for(int i = 0; i < r; ++i) {
            for(int j = 0; j < p; ++j) {
                need_r[i][j] = make_pair(n[j][i], j);
            }
        }
        for(int i = 0; i < m; ++i) {
            available[R[i]]--;
            need_r[R[i]][P[i]].first--;
            used_r[P[i]][R[i]]++;
        }
        for(int i = 0; i < r; ++i) {
            sort(begin(need_r[i]), end(need_r[i]));
        }
        for(int i = 0; i < r; ++i) {
            while(pos[i] < p && (need_r[i][pos[i]].first == 0 || available[i] >= need_r[i][pos[i]].first)) {
                int process_id = need_r[i][pos[i]].second;
                if(++cnt[process_id] == r) {
                    term_process.push(process_id);
                }
                pos[i]++;
            }
        }
        while(!term_process.empty()) {
            int idx = term_process.front();
            term_process.pop();
            for(int i = 0; i < r; ++i) {
                available[i] += used_r[idx][i];
                while(pos[i] < p && available[i] >= need_r[i][pos[i]].first) {
                    int process_id = need_r[i][pos[i]].second;
                    if(++cnt[process_id] == r) {
                        term_process.push(process_id);
                    }
                    pos[i]++;
                }
            }
        }
        if(count(begin(cnt), end(cnt), r) == p) {
            lb = m;
        } else {
            ub = m;
        }
    }
    if(ub == t + 1) {
        cout << -1 << endl;
    } else {
        cout << ub << endl;
    }
}