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;

typedef long long ll;
typedef pair<int, int> pii;

#define debug(a) cout << #a << ": " << a << endl
#define debuga1(a, l, r) fto(i, l, r) cout << a[i] << " "; cout << endl
#define fdto(i, r, l) for(int i = (r); i >= (l); --i)
#define fto(i, l, r) for(int i = (l); i <= (r); ++i)
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define sz(a) (int)a.size()

const double PI = acos(-1.0);

double fRand(double fMin, double fMax)
{
    double f = (double)rand() / RAND_MAX;
    return fMin + f * (fMax - fMin);
}

template <class T>
T min(T a, T b, T c) {
    return min(a, min(b, c));
}

template <class T>
T max(T a, T b, T c) {
    return max(a, max(b, c));
}

const int MAXN = 305;
const int MAXT = 200005;

int n, m, t, c[MAXN][MAXN], l[MAXN], p[MAXT], r[MAXT];

bool check(int mid) {
    vector<int> ins(m), cntSat(n, 0), pos(m, 0);
    vector<vector<int> > req(n, vector<int>(m));
    vector<vector<pii> > ord(m, vector<pii>());

//    debug(mid);
    fto(j, 0, m-1) {
        ins[j] = l[j];
        fto(i, 0, n-1)
            req[i][j] = c[i][j];
    }

    int cntFinish = 0;
    fto(i, 1, mid) {
        --ins[r[i]];
        --req[p[i]][r[i]];
    }

    fto(i, 0, n-1) {
        bool term = true;
        fto(j, 0, m-1)
            if (req[i][j] > 0)
                term = false;
        if (term) {
            ++cntFinish;
            fto(j, 0, m-1)
                ins[j] += c[i][j];
        } else {
            fto(j, 0, m-1)
                ord[j].pb({req[i][j], i});
        }
    }

    fto(j, 0, m-1)
        sort(ord[j].begin(), ord[j].end());

//    fto(i, 0, n-1) {
//        fto(j, 0, m-1) printf("%d ", req[i][j]);
//        puts("");
//    }
//    fto(i, 0, m-1) printf("%d ", ins[i]);
//    puts("");
//
//    fto(j, 0, m-1) {
//        for(pii p: ord[j]) printf("%d %d %d\n", j, p.ff, p.ss);
//    }

    queue<int> q;
    fto(j, 0, m-1) {
        int &i = pos[j];
        while (i < sz(ord[j]) && ord[j][i].ff <= ins[j]) {
            int id = ord[j][i].ss;
            ++cntSat[id];
            if (cntSat[id] == m)
                q.push(id);
            ++i;
        }
    }

//    fto(i, 0, n-1) printf("%d ", cntSat[i]);
//    puts("");

    while (!q.empty()) {
        int i = q.front(); q.pop();
        ++cntFinish;
        fto(j, 0, m-1) {
            ins[j] += c[i][j] - req[i][j];
            int &i = pos[j];
            while (i < sz(ord[j]) && ord[j][i].ff <= ins[j]) {
                int id = ord[j][i].ss;
                ++cntSat[id];
                if (cntSat[id] == m)
                    q.push(id);
                ++i;
            }
        }
    }

    return (cntFinish == n);
}

int main () {
    scanf("%d%d%d", &n, &m, &t);
    fto(i, 0, m-1) scanf("%d", &l[i]);
    fto(i, 0, n-1)
        fto(j, 0, m-1)
            scanf("%d", &c[i][j]);
    fto(i, 1, t) {
        scanf("%d%d", &p[i], &r[i]);
        --p[i]; --r[i];
    }

    check(0);
//    debug(maxFinish);

    int lo = 1, hi = t, res = -1;
    while (lo <= hi) {
        int mid = (lo+hi)/2;
//        debug(mid);
        if (!check(mid)) {
            res = mid;
            hi = mid-1;
        } else lo = mid+1;
    }

    printf("%d\n", res);

    return 0;
}