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 <vector>
#include <cstring>

using namespace std;

int initNeed[300][300];

class State {
private:
	int processNum;
	int resourceNum;
	int need[300][300];
	int needSum[300];
	int rest[300];
	int terminate[300];
public:
	void initialize(int p, int r){
		processNum = p;
		resourceNum = r;
		for(int i=0;i<r;i++) cin >> rest[i];
		for(int i=0;i<p;i++){
			for(int j=0;j<r;j++) cin >> need[i][j];
			needSum[i] = 0;
			for(int j=0;j<r;j++) needSum[i] += need[i][j];
		}
		memcpy(initNeed, need, sizeof(need));
		for(int i=0;i<p;i++) terminate[i] = 0;
	}
	void progress(int P, int R){
		--need[P][R];
		--needSum[P];
		--rest[R];
		if(needSum[P] == 0){
			for(int i=0;i<resourceNum;i++){
				rest[i] += initNeed[P][i];
			}
			terminate[P] = 1;
		}
	}
	bool valid(){
		while(true){
			bool update = false;
			for(int i=0;i<processNum;++i){
				if(terminate[i]) continue;
				bool ok = true;
				for(int j=0;j<resourceNum;j++){
					if(need[i][j] > rest[j]){ ok = false; break; }
				}
				if(ok){
					terminate[i] = 1;
					for(int j=0;j<resourceNum;++j){
						rest[j] += initNeed[i][j] - need[i][j];
					}
					update = true;
				}
			}
			if(!update) break;
		}
		for(int i=0;i<processNum;++i) if(!terminate[i]) return false;
		return true;
	}
};

int main(){
	int p, r, t;
	while(cin >> p >> r >> t){
		State s; s.initialize(p, r);
		vector<int> P(t), R(t);
		for(int i=0;i<t;i++){
			cin >> P[i]; --P[i];
			cin >> R[i]; --R[i];
		}
		s.progress(P[0], R[0]);
		State m, v;
		int low = 0, high = t;
		while(high - low > 1){
			int mid = (low+high)/2;
			m = s;
			for(int i=low+1;i<=mid;i++){
				m.progress(P[i], R[i]);
			}
			v = m;
			if(v.valid()){
				low = mid;
				s = m;
			} else {
				high = mid;
			}
		}
		cout << (low==t-1 ? -1 : low+2) << endl;
	}
}