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 <array>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <tuple>
#include <bitset>
#include <memory>
#include <cmath>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <cfloat>
bool is_deadlocked(std::vector<int> resource_stock, std::vector<std::vector<int>> resource_reserved, const std::vector<std::vector<int>> &resource_need) {
	std::queue<int> terminated;
	for (auto i = 0; i < resource_need.size(); ++i) {
		bool can_execute = true;
		for (auto r = 0; r < resource_stock.size(); ++r) {
			if (std::max(0, resource_stock[r]) + resource_reserved[i][r] < resource_need[i][r]) {
				can_execute = false;
				break;
			}
		}
		if (!can_execute) terminated.push(i);
		else {
			for (auto r = 0; r < resource_stock.size(); ++r) {
				resource_stock[r] += resource_reserved[i][r];
			}
		}
	}
	while (!terminated.empty()) {
		auto count = terminated.size();
		for (auto c = 0; c < count; ++c) {
			auto process = terminated.front(); terminated.pop();
			bool can_execute = true;
			for (auto r = 0; r < resource_stock.size(); ++r) {
				if (std::max(0, resource_stock[r]) + resource_reserved[process][r] < resource_need[process][r]) {
					can_execute = false;
					break;
				}
			}
			if (!can_execute) terminated.push(process);
			else {
				for (auto r = 0; r < resource_stock.size(); ++r) {
					resource_stock[r] += resource_reserved[process][r];
				}
			}
		}
		if (count == terminated.size()) return true;
	}
	return false;
}
bool is_deadlocked(std::vector<int> resource_stock, std::vector<std::vector<std::vector<int>>> rock_history, const std::vector<std::vector<int>>& resource_need, const int current_time) {
	std::vector<std::vector<int>> resource_reserved;
	std::transform(rock_history.begin(), rock_history.end(), std::back_inserter(resource_reserved), 
		[current_time](const std::vector<std::vector<int>>& histories) {
		std::vector<int> resource;
		std::transform(histories.begin(), histories.end(), std::back_inserter(resource), 
			[current_time](const std::vector<int>& history) {return std::distance(std::begin(history), std::upper_bound(std::begin(history), std::end(history), current_time)); });
		return resource;
		});
	for (const auto &reserved : resource_reserved) {
		for (auto i = 0; i < resource_stock.size(); ++i)
			resource_stock[i] -= reserved[i];
	}
	return is_deadlocked(resource_stock, resource_reserved, resource_need);
}
int main() {
	int p, r, t; std::cin >> p >> r >> t;
	std::vector<int> stock(r); for (auto& s : stock) std::cin >> s;
	std::vector<std::vector<int>> resource_needs(p, std::vector<int>(r));
	for (auto& needs : resource_needs) for (auto& resource : needs) std::cin >> resource;
	std::vector<std::vector<std::vector<int>>> rock_history(p, std::vector<std::vector<int>>(r));
	for (auto i = 1; i <= t; ++i) {
		int proc, res; std::cin >> proc >> res;
		rock_history[proc - 1][res - 1].push_back(i);
	}
	int min = 1, max = t + 1;
	while (min < max) {
		const auto mid = (min + max) / 2;
		if (is_deadlocked(stock, rock_history, resource_needs, mid)) max = mid;
		else min = mid + 1;
	}
	std::cout << ((max > t) ? -1 : max) << '\n';
}