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;
typedef long long ll;
typedef pair<int,int> pii;

/*
  ????????§????????§?????????????????????????????????????????????????????????
  ??????????????????????????????????????????????????????, ?????¨??????????????????????????????????????°????±??????????????????°????????????
  O(P)?¨??????§?????????????????????????????§????????????
  ?§£?????§?????????????????????????§£??????????????¨, ????????????????¶???????????????????????????¨????????±
  ????????????????????????
 */

int P,R,T;
int L[301];
int N[301][301];
int PS[200010];
int RS[200010];

// ??°????????????????????????????????????????????????
int user[301][301];
// ??????????????????????????????????????£????????????
int leftr[301];

bool check(int mid){
    // mid???????????§, ??????????????????????????????????????§????????????
    // ??????????????????????????????????´???????????????????????????????????????????
    // resource??????????????????????????????????´????, ?????????resource????§£???????????????
    memset(user,0,sizeof(user));
    for(int i = 0; i < R; i++)
        leftr[i] = L[i];
    // mid???????´??????§, ?¨??????????
    for(int i = 0; i <= mid; i++){
        int who = PS[i];  who--;
        int where = RS[i]; where--;
        user[who][where]++;
        leftr[where]--;
    }
    for(int i = 0; i < P; i++){
        int cnt = 0;
        for(int j = 0; j < R; j++) if(user[i][j] == N[i][j]) cnt++;
        if(cnt == R){
            for(int j = 0; j < R; j++){
                user[i][j] = 0;
                leftr[j] += N[i][j];
            }
        }
    }
    
    // ???????????§, resource???????????????????????????????????????????±????, ??????????????????????§£?????§??????????????????
    // ?§£?????§????????????ok
    // ????????????ng
    bool is_updated = true;
    while(is_updated){
        is_updated = false;
        for(int i = 0; i < P; i++){
            int cnt = 0;
            for(int j = 0; j < R; j++)
                cnt += user[i][j];
            if(cnt != 0){
                int free = 0;
                // ?§£?????§??????????????????
                for(int j = 0; j < R; j++){
                    if(user[i][j] + leftr[j] >= N[i][j]){
                        free++;
                    }
                }
                if(free == R){
                    is_updated = true;
                    for(int j = 0; j < R; j++){
                        leftr[j] += user[i][j];
                        user[i][j] = 0;
                    }
                    break;
                }
                else{
                    continue;
                }
            }

        }
    }
    int cnt = 0;
    for(int i = 0; i < P; i++){
        for(int j = 0; j < R; j++)
            cnt += user[i][j];
    }
    return cnt > 0;
}

int main(){

    cin>>P>>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>>PS[i]>>RS[i];
    
    // ????????????????????????????????????????????§, ?????????????????§???????????????????????????????????????????????????????????¢?´¢
    // ?????????????????????????????´???????????????
    int lb = -1;
    int ub = T;
    while(ub - lb > 1){
        int mid = (ub + lb) / 2;
        if(check(mid)) ub = mid;
        else lb = mid;
    }
    if(ub == T) cout<<-1<<endl;
    else cout<<ub+1<<endl;
    
    return 0;
}