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;

#define int long long

struct Log {
	int p, r;
};

typedef pair<int, int> Pair;

int P, R, T;
vector< vector<int> > p0;
vector<int> r0;
vector<Log> g;
bool isAlive(int t) {
	vector< vector<int> > p = p0;
	vector<int> r = r0;
	for (int i = 0; i < t; ++i) {
		--p[g[i].p][g[i].r];
		--r[g[i].r];
	}
	vector<bool> isFree(P, false);
	for (int i = 0; i < P; ++i) {
		int cnt = 0;
		for (int j = 0; j < R; ++j) {
			cnt += p[i][j] == 0;
		}
		if (cnt == R) {
			isFree[i] = true;
			for (int j = 0; j < R; ++j) {
				r[j] += p0[i][j];
			}
		}
	}

	vector<int> deadCount(P, 0);
	vector<bool> isDead(P, false);
	vector< set<Pair> > need(R);
	for (int i = 0; i < P; ++i) {
		for (int j = 0; j < R; ++j) {
			if (p[i][j] > r[j]) {
				need[j].insert( Pair(p[i][j], i) );
				++deadCount[i];
				isDead[i] = true;
			}
		}
	}

	queue<Pair> Q;
	for (int i = 0; i < P; ++i) {
		if (!isFree[i] && !isDead[i]) {
			isFree[i] = true;
			for (int j = 0; j < R; ++j) {
				Q.push( Pair(j, p0[i][j]-p[i][j]) );
			}
		}
	}
	while ( !Q.empty() ) {
		Pair q = Q.front(); Q.pop();
		int rid = q.first, amount = q.second;
		r[rid] += amount;
		while (need[rid].size() > 0) {
			set<Pair>::iterator it = need[rid].begin();
			if (it->first <= r[rid]) {
				if (--deadCount[it->second] == 0) {
					isDead[it->second] = false;
					isFree[it->second] = true;
					for (int j = 0; j < R; ++j) {
						Q.push( Pair(j, p0[it->second][j]-p[it->second][j]) );
					}
				}
				need[rid].erase(it);
			}
			else {
				break;
			}
		}
	}
	for (int i = 0; i < P; ++i) {
		if (isDead[i]) return false;
	}

	return true;
}

signed main() {
	cin >> P >> R >> T;
	r0 = vector<int>(R);
	p0 = vector< vector<int> >(P, vector<int>(R));
	g.resize(T);
	for (int i = 0; i < R; ++i) cin >> r0[i];
	for (int i = 0; i < P; ++i) {
		for (int j = 0; j < R; ++j) {
			cin >> p0[i][j];
		}
	}
	for (int t = 0; t < T; ++t) {
		cin >> g[t].p >> g[t].r; --g[t].p, --g[t].r;
	}

	int left = 0, right = T+1;
	while ( right-left > 1 ) {
		int m = (left+right)/2;
		if ( isAlive(m) ) {
			left = m;
		}
		else {
			right = m;
		}
	}
	if (right == T+1) cout << -1 << endl;
	else cout << right << endl;
}