Submission #1477326

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <array>
#include <cassert>
#include <bitset>
using namespace std;
using LL = long long;

LL W, H, Q;
struct B
{
	LL pos, tim, wid;
	B(LL p, LL t, LL w) :pos(p), tim(t), wid(w)
	{}
};
vector<B>xbeam, ybeam;

LL walk(vector<B>& beam, LL span)
{
	sort(beam.begin(), beam.end(), [](const B&b1, const B&b2)
	{
		if (b1.tim == b2.tim)return b1.pos < b2.pos;
		return b1.tim < b2.tim;
	});
	for (auto itr = beam.begin(); itr != beam.end() && (itr + 1) != beam.end(); ++itr)
	{
		auto nxt = itr + 1;
		while (nxt != beam.end() && itr->tim == nxt->tim && itr->pos + itr->wid >= nxt->pos)
		{
			itr->wid++;
			nxt = beam.erase(nxt);
		}
	}
	vector<LL>dp(span, 0);
	for (auto b : beam)
	{
		LL lef = b.pos - 1;
		LL rht = b.pos + b.wid;
		LL lval = (lef < 0) ? INT_MAX : dp[lef];
		LL rval = (rht >= span) ? INT_MAX : dp[rht];
		for (LL i = lef + 1; i < rht; ++i)
		{
			LL val = min(lval + abs(i - lef), rval + abs(i - rht));
			dp[i] = val;
		}
	}
	LL ans = INT_MAX;
	for (auto elm : dp)ans = min(ans, elm);
	return (ans == INT_MAX) ? -1 : ans;
}

int main(void)
{
	cin >> W >> H >> Q;
	for (int i = 0; i < Q; ++i)
	{
		LL t, d, x;
		cin >> t >> d >> x;
		--x;
		if (d == 0)
		{
			xbeam.push_back(B(x, t, 1));
		}
		else
		{
			ybeam.push_back(B(x, t, 1));
		}
	}
	LL r1 = walk(xbeam, W);
	LL r2 = walk(ybeam, H);
	if (r1 < 0 || r2 < 0)
	{
		cout << -1 << endl;
		return 0;
	}
	cout << r1 + r2 << endl;
	return 0;
}

Submission Info

Judge Result