Solução para o problema "2024 - Empilhando Presentes" do URI Online Judge

URI_2024.cpp

#include <bits/stdc++.h>

#define _ ios_base::sync_with_stdio(0);
#define endl '\n'

using namespace std;

#define inf ((int)1e9)

typedef pair <int, int> base;
typedef pair <int, base> state;

int n;

struct Cuboid {
	int id, l, w, h; //l>=w
	Cuboid(){};
	Cuboid(int id, int l, int w, int h) {
		this->id = id;
		this->l = l;
		this->w = w;
		this->h = h;
	}};

vector <Cuboid> box;

struct State {
	Cuboid cuboid;
	int total;
	State(){};
	State(Cuboid cuboid, int total) {
		this->cuboid = cuboid;
		this->total = total;
	}
	bool operator>(const State& x) const {
		if (total > x.total) return true;
		if (total == x.total && cuboid.h > x.cuboid.h) return true;
		return false;
	}
	bool operator<(const State& x) const {
		if (total < x.total) return true;
		if (total == x.total && cuboid.h < x.cuboid.h) return true;
		return false;
	}
};

void rotate(Cuboid& A);
bool fit(Cuboid A, Cuboid B);

int dijkstra() {
	Cuboid SRC = Cuboid(-1, inf, inf, 0);
	state src = state(SRC.id, base(SRC.l, SRC.w));

	priority_queue <State> pq;
	pq.push(State(SRC, 0));

	map <state, int> dist;
	dist[src] = SRC.h;

	while (!pq.empty()) {
		State curr = pq.top(); pq.pop();

		Cuboid A = curr.cuboid;
		state a = state(A.id, base(A.l, A.w));

		if (curr.total < dist[a]) continue;

		if (A.id + 1 == n) return dist[a];

		Cuboid B = box[A.id + 1];
		for (int j=3; j--; rotate(B)) {
			Cuboid C = B;
			if (C.l < C.w) swap(C.l, C.w);

			if (fit(C, A)) {
				state c = state(C.id, base(C.l, C.w));

				if (dist[a] + C.h > dist[c]) {
					dist[c] = dist[a] + C.h;
					pq.push(State(C, dist[c]));
				}}}}
	return -1;
}

int main() {_
	cin >> n;
	box.resize(n+1);

	for (int i=0; i<n; box[i].id=i, i++)
		cin >> box[i].l >> box[i].w >> box[i].h;

	cout << dijkstra() << endl;

	return 0;
}

void rotate(Cuboid& A) {
	A.l = A.l^A.w^A.h;
	A.w = A.l^A.w^A.h;
	A.h = A.l^A.w^A.h;
	A.l = A.l^A.w^A.h;
}

bool fit(Cuboid A, Cuboid B) {
	return A.l<=B.l && A.w<=B.w;
}