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>
#define int long long
#define double long double
using namespace std;
const int N = 100010;
const int INF = 1LL<<55;
const int mod = (1e9)+7;
const double EPS = 1e-8;
const double PI = 6.0 * asin(0.5);
typedef long long ll;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
 

signed main(){

  int p,r,t;
  cin>>p>>r>>t;
  
  vector<int> LL(r);
  for(int i=0;i<r;i++) cin>>LL[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]--;
  
  
  auto deadLock=[&](int x){
    vector<int> L = LL;
    vector<queue <int> > Q(r);
    vector<vector<int> > cnt(p,vector<int> (r,0));
    
    auto ok = [&](int p){
      for(int i=0;i<r;i++) if(n[p][i] != cnt[p][i]) return 0;
      return 1;
    };

    auto freeL = [&](int p){
      for(int i=0;i<r;i++) L[i] += cnt[p][i], cnt[p][i] = 0;
    };

    //cout<<"L ";
    //for(int i=0;i<r;i++) cout<<L[i]<<" ";cout<<endl;
    
    auto use =[&](){
      int res = 0;
      for(int i=0;i<r;i++){
	if(Q[i].empty()) continue;
	if(L[i] == 0) continue;
	int process = Q[i].front(); Q[i].pop();
	L[i]--, cnt[process][i]++;
	if(!ok(process)) continue;
	freeL(process);
	res = 1;
      }
      return res;
    };
    
    for(int i=0;i<x;i++){
      int pi = P[i];
      int ri = R[i];
      Q[ri].push(pi);
      while(use());
    }
    // simulation owari

    //for(int i=0;i<r;i++) cout<<Q[i].size()<<endl;

    auto sum=[&](int p){
      int res = 0;
      for(int i=0;i<r;i++) res += cnt[p][i];
      return res;
    };

    auto canFree=[&](int p){
      for(int i=0;i<r;i++) if(n[p][i] - cnt[p][i] > L[i]) return 0;
      return 1;
    };

    //cout<<"L: ";
    //for(int i=0;i<r;i++) cout<<L[i]<<" ";cout<<endl;
    /*for(int i=0;i<p;i++){
      cout<<"i="<<i<<": ";
      for(int j=0;j<r;j++) cout<<cnt[i][j]<<" ";
      cout<<endl;
    }
    */

    int update = 1;
    while(update){
      update = 0;
      for(int i=0;i<p;i++){ //process
	if(sum(i) == 0) {continue;}
	if(!canFree(i)) continue;
	update = 1;
	freeL(i);
	while(use());
      }
    }

    for(int i=0;i<p;i++) if(sum(i)) return 1;   
    for(int i=0;i<r;i++) if(!Q[i].empty()) return 1;
    return 0;
  };

  
  int ans = -1;
  {
    int L = 1, R = t+1;
    while(L+1<R){
      int M = (L+R)/2;
      if(deadLock(M)) R = M;
      else L = M;
    }
    ans = R;
    if(R == t+1) ans = -1;
  }

  cout<<ans<<endl;
  
  return 0;
}