Submission #1159891

---

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){
            set<int> p,q;
            for(int x:b[i][t]){
                p.insert(x);
                if(x-1>=0) q.insert(x-1);
                if(x+1<wh[i]) q.insert(x+1);
            }
            for(auto x:q){
                if(p.find(x)!=p.end()) continue;
                for(int x_=x-1; x_>=0 and p.find(x_)!=p.end(); --x_) dp[x]=min(dp[x],dp[x_]+x-x_);
                for(int x_=x+1; x_<wh[i] and p.find(x_)!=p.end(); ++x_) dp[x]=min(dp[x],dp[x_]+x_-x);
            }
            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