1840F - Railguns - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define VI vector<int>
#define ll long long
#define ull unsigned ll
#define lll __int128
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define endl "\n"
template<class T>inline void read(T &x) {
    x=0; char ch=getchar(); bool f=0;
    for(;ch<'0'||ch>'9';ch=getchar()) f|=(ch=='-');
    for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+(ch^48);
    if(f) x=-x;
}
template<class T,class... V>
inline void read(T &a,V&... b){read(a); read(b...);}
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int N = 1e4 + 5;
const int M = 105;
const int inf = 2e9;

struct node{
    int t,d,c;
    friend inline bool operator < (const node &A, const node &B) {
        return A.t < B.t;
    }
};
node a[M];
int n,m,q;
void Solve() {
    read(n,m,q);
    fo(i,1,q) {
        int t,d,c;
        read(t,d,c);
        a[i] = {t,d,c};
    }
    sort(a+1,a+q+1);
    vector<vector<int>> v, w;
    v.resize(n+2); w.resize(n+2);
    ff(i,0,n+2)
        v[i].resize(m+2), w[i].resize(m+2);
    for(int x=0;x<=n;x++)
        for(int y=0;y<=m;y++)
            v[x][y] = 0;
    v[0][0] = 1;
    a[0] = {0,0,0};
    int ans = inf;
    for(int i=1,j;i<=q;i=j) {
        int ot = a[i].t - a[i-1].t;
        for(int x=0;x<=n;x++) {
            for(int y=0;y<=m;y++) {
                if(v[x][y]) {
                    if((n-x)+(m-y) < ot) {
                        ans = min(ans, a[i-1].t + (n-x) + (m-y));
                    }
                    w[x][y] = ot + 1;
                }
                else {
                    w[x][y] = max(0,max(x ? (w[x-1][y] - 1) : 0, y ? (w[x][y-1] - 1) : 0));
                }
            }
        }
        if(ans != inf) {
            printf("%d\n",ans);
            return;
        }
        for(j=i;j<=q&&a[j].t==a[i].t;j++) {
            if(a[j].d == 1)
                for(int y=0;y<=m;y++)
                    w[a[j].c][y] = 0;
            else
                for(int x=0;x<=n;x++)
                    w[x][a[j].c] = 0;
        }
        for(int x=0;x<=n;x++)
            for(int y=0;y<=m;y++)
                if(w[x][y])
                    v[x][y] = 1, w[x][y] = 0;
                else
                    v[x][y] = 0;
    }
    for(int x=0;x<=n;x++)
        for(int y=0;y<=m;y++)
            if(v[x][y])
                ans = min(ans, a[q].t + (n-x)+(m-y));
    if(ans == inf) {
        puts("-1");
    }
    else {
        printf("%d\n", ans);
    }
}
int main() {
    int T = 1;
    read(T);
    for(;T--;) Solve();
    return 0;
}