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 <iostream>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
typedef long long ll;

int main(){
    int p,r,t;
    cin >> p >> r >> t;
    vector<int> l(r);
    for(int i=0;i<r;i++){
        cin >> l[i];
    }
    vector<vector<int> > n(p,vector<int>(r));
    for(int i=0;i<p;i++){
        for(int j=0;j<r;j++){
            cin >> n[i][j];
        }
    }
    vector<int> P(t),R(t);
    for(int i=0;i<t;i++){
        cin >> P[i] >> R[i];
        P[i]--;
        R[i]--;
    }
    int ok = -1;
    int ng = t+1;
    while(abs(ok-ng)!=1){
        int mid = (ok+ng)/2;
        //cout << mid << endl;
        vector<int> x(r);
        vector<vector<int> > y(p,vector<int>(r));
        for(int i=0;i<r;i++){
            x[i] = l[i];
        }
        for(int i=0;i<p;i++){
            for(int j=0;j<r;j++){
                y[i][j] = n[i][j];
            }
        }
        for(int i=0;i<mid;i++){
            x[R[i]]--;
            y[P[i]][R[i]]--;
            if(y[P[i]][R[i]]==0){
                bool flag = 1;
                for(int j=0;j<r;j++){
                    if(y[P[i]][j]!=0){
                        flag = 0;
                        break;
                    }
                }
                if(flag){
                    for(int j=0;j<r;j++){
                        y[P[i]][j]=n[P[i]][j];
                        x[j] += n[P[i]][j];
                    }
                }
            }
        }
        vector<bool> sss(p);
        for(int z=0;z<p;z++){
            for(int i=0;i<p;i++){
                if(sss[i]==1)continue;
                bool flag = 1;
                for(int k=0;k<r;k++){
                    //cout << i << " " << k << " " << y[i][k] << " " <<x[k] << endl;
                    if(y[i][k]>x[k]){
                        flag=0;
                        break;
                    }
                }
                if(flag){
                    sss[i]=1;
                    for(int k=0;k<r;k++){
                        x[k] += n[i][k]-y[i][k];
                    }
                }
            }
        }
        bool flag = 1;
        for(int i=0;i<p;i++){
            if(sss[i]==0){
                flag = 0;
            }
        }
        if(flag){
            ok = mid;
        }else{
            ng = mid;
        }
    }
    if(ng==t+1){
        cout << -1 << endl;
    }else{
    cout << ng << endl;
    }
    return 0;
}