Submission #1159767

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif

const int inf=1e9;
const int64_t inf64=1e18;
const double eps=1e-9;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}

using i64=int64_t;

void solve(){
    int wh[2],q;
    cin >> wh[0] >> wh[1] >> q;
    vector<int> b[2][100000];
    rep(i,0,q){
        int t,d,x;
        cin >> t >> d >> x;
        --x;
        --t;
        b[d][t].push_back(x);
    }

    static int dp[100000],ans=0;
    rep(i,0,2){
        fill_n((int*)dp,100000,0);
        rep(t,0,100000){
            for(int x:b[i][t]){
                rep(j,-1,2){
                    int x_=x+j;
                    if(x_<0 or wh[i]<=x_) continue;
                    dp[x_]=min(dp[x_],dp[x]+1);
                }
            }
            for(int x:b[i][t]) dp[x]=inf;
        }
        int tmp=inf;
        rep(j,0,wh[i]) tmp=min(tmp,dp[j]);
        if(tmp>=inf){
            cout << -1 << endl;
            return;
        }
        ans+=tmp;
    }
    cout << ans << endl;
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(10);
    solve();
    return 0;
}

Submission Info

Judge Result