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 <algorithm>
#include <numeric>
#include <list>
#include <cassert>
using namespace std;

template<typename T>
void fill_all(T& a, const T& b)
{
	a = b;
}
template<typename T, size_t N, typename U>
void fill_all(T(& a)[N], const U& b)
{
	for (auto& i : a)
	{
		fill_all(i, b);
	}
}

#if 1
int P, R, Q;
int r_num[500];//r
int cost[500][500];//i,r
int rem[500][500];//i,r
std::list<int>::iterator resolved_iter[500][500];//r,i
std::list<int> resolved[500][501];//r,num
std::pair<int, int> Log[300000];
bool ended[500];
int ended_num;

void run_end(int p)
{
	assert(!ended[p]);
	ended[p] = true;
	++ended_num;
	//for (int r = 0; r < R; r++)
	//{
	//	resolved[r][rem[p][r]].erase(resolved_iter[r][p]);
	//}
	for (int r = 0; r < R; r++)
	{
		r_num[r] += (cost[p][r] - rem[p][r]);
	}
}
void jump()
{
	bool ok = false;
	for (int p = 0; p < P; p++)
	{
		if (ended[p]) { continue; }
		ok = true;
		for (int r = 0; r < R; r++)
		{
			if (rem[p][r] > r_num[r]) {
				ok = false;
				break;
			}
		}
		if (ok) {
			run_end(p);
			break;
		}
	}
	if (ok) {
		jump();
	}
}

int main()
{
	cin >> P >> R >> Q;
	for (int i = 0; i < R; i++)
	{
		cin >> r_num[i];
	}
	for (int i = 0; i < P; i++)
	{
		for (int r = 0; r < R; r++)
		{
			cin >> cost[i][r];
			rem[i][r] = cost[i][r];
		}
	}

	for (int i = 0; i < Q; i++)
	{
		cin >> Log[i].first >> Log[i].second; --Log[i].first; --Log[i].second;
		auto p = Log[i].first;
		assert(!ended[p]);
		--rem[p][Log[i].second];
		--r_num[Log[i].second];
		assert(Log[i].second >= 0);
		assert(Log[i].second < 300);
		assert(r_num[Log[i].second] <= 100);
		assert(r_num[Log[i].second] >= 0);

		if (rem[p][Log[i].second] == 0) {
			bool ok = true;
			for (int r = 0; r < R; r++)
			{
				if (rem[p][r] > 0) {
					ok = false;
					break;
				}
			}
			if (ok) {
				assert(!ended[p]);
				ended[p] = true;
				++ended_num;
				for (int r = 0; r < R; r++)
				{
					r_num[r] += cost[p][r];
					assert(r_num[r] <= 100);
				}
			}
		}
	}
	for (int i = 0; i < P; i++)
	{
		for (int r = 0; r < R; r++)
		{
			assert(rem[i][r] >= 0);
			assert(rem[i][r] <= 100);
			resolved[r][rem[i][r]].push_front(i);
			resolved_iter[r][i] = resolved[r][rem[i][r]].begin();
		}
	}
	jump();
	if (ended_num == P) {
		cout << -1 << endl;
		return 0;
	}

	int q = Q - 1;
	for (; q >= 0; --q)
	{
		auto r = Log[q].second;
		{
			auto p = Log[q].first;
			if (!ended[p]) {
				resolved[r][rem[p][r]].erase(resolved_iter[r][p]);
				++rem[p][r];
				resolved[r][rem[p][r]].push_front(p);
				resolved_iter[r][p] = resolved[r][rem[p][r]].begin();
				++r_num[r];
			}
		}

		bool ok = false;
		for(auto& p : resolved[r][r_num[r]]) {
			if (ended[p]) { continue; }
			ok = true;
			for (int rr = 0; rr < R; rr++)
			{
				if (rem[p][rr] > r_num[rr]) {
					ok = false;
					break;
				}
			}
			if (ok) {
				run_end(p);
				break;
			}
		}
		if (ok) {
			jump();
		}

		if (ended_num >= P) {
			break;
		}
	}
	cout << (q+1) << endl;
}
#endif