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 <math.h>
#include <string.h>
#include <cstdio>
#include <vector>
#include <set>
#include <cassert>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <functional>
#include <iomanip>
//#include <windows.h>  //Should be deleted when using AtCoder&POJ
using namespace std;

#define ll long long
#define pii pair<int,int>
#define qi ios::sync_with_stdio(0)
/**==Info==
*Program:2
*Problem:Deadlock Detection
*Date:2019-7-5
*Algorithm:Binary Search
*Stats:AC-Aizu1361*/

bool debug=false;

int n,m;
int need[305][305];
int r[305];

pii op[200005];
int t;

int tneed[305][305];
int tr[305];

int zero[305];

bool run[305];

void recover(int pid){
	for(int i=0;i<m;i++){
		tr[i]+=need[pid][i]-tneed[pid][i];
		tneed[pid][i]=need[pid][i];
	}
}

bool ok(int mid){
////	cout<<"checking"<<mid<<endl;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			tneed[i][j]=need[i][j];
		}
	}
	for(int i=0;i<m;i++){
		tr[i]=r[i];
	}
	memset(zero,0,sizeof(zero));
	memset(run,0,sizeof(run));
	
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(tneed[i][j]==0){
				zero[i]++;
			}
		}
	}
	
//	cout<<"ptp"<<endl;
	
	for(int i=0;i<=mid;i++){
		tr[op[i].second]--;
		tneed[op[i].first][op[i].second]--;
		run[op[i].first]=true;
		if(tneed[op[i].first][op[i].second]==0){
			zero[op[i].first]++;
		}
		if(zero[op[i].first]==m){
			run[op[i].first]=false;
			zero[op[i].first]=0;
			recover(op[i].first);
			for(int j=0;j<m;j++){
				if(tneed[op[i].first][j]==0){
					zero[op[i].first]++;
				}
			}
		}
	}
	
//	cout<<"ptp 2"<<endl;
//	for(int i=0;i<n;i++){
//		for(int j=0;j<m;j++){
//			cout<<tneed[i][j]<<' ';
//		}
//		cout<<endl;
//	}	
//	cout<<endl;
	
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(!run[j]){
				continue;
			}
			
			//check it
			bool ok=true;
			for(int k=0;k<m;k++){
				if(tr[k]<tneed[j][k]){
					ok=false;
					break;
				}
			}
			if(ok){
				recover(j);
				run[j]=false;
			}
		}
	}
	
//	cout<<"ptp 3"<<endl;
	
	for(int i=0;i<n;i++){
		if(run[i]){
			return true;
		}
	}
	return false;
}
int main(int argc,char* argv[]){
//	freopen("test.txt","r",stdin);
	qi;
	cin>>n>>m>>t;
	for(int i=0;i<m;i++){
		cin>>r[i];
	}
	
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>need[i][j];
		}
	}
	
	for(int i=0;i<t;i++){
		cin>>op[i].first>>op[i].second;
		op[i].first--;
		op[i].second--;
	}
	
	
	int l=0,r=t-1,res=-2;
	while(l<=r){
		int mid=(l+r)/2;
		if(ok(mid)){
			res=mid;
			r=mid-1;
		}else{
			l=mid+1;
		}
	}
	
	cout<<res+1<<endl;
	return 0;
}