Submission #101179

#	Time	Username	Problem	Language	Result	Execution time	Memory
101179		E869120	Wall (CEOI14_wall)	C++14	30 / 100	1694 ms	43228 KiB

wall

#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#include <tuple>
using namespace std;

long long dist[44][44][1024];
int H, W, P[1009][1009], A[1009][1009], B[1009][1009];
int cp[44][44][4], cq[44][44][4];
vector<pair<int, int>>L;

int main() {
	cin >> H >> W;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) { cin >> P[i][j]; if (P[i][j] >= 1) L.push_back(make_pair(i, j)); }
	}
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W + 1; j++) {
			cin >> A[i][j];
			cq[i][j][1] = A[i][j]; cq[i + 1][j][3] = A[i][j];
		}
	}
	for (int i = 0; i < H + 1; i++) {
		for (int j = 0; j < W; j++) {
			cin >> B[i][j];
			cq[i][j][0] = B[i][j]; cq[i][j + 1][2] = B[i][j];
			for (int k = 0; k < L.size(); k++) {
				if (L[k].second == j && L[k].first >= i) { cp[i][j][0] += (1 << k); cp[i][j + 1][2] += (1 << k); }
			}
		}
	}

	for (int i = 0; i <= H; i++) { for (int j = 0; j <= W; j++) { for (int k = 0; k < 1024; k++) dist[i][j][k] = (1LL << 60); } }

	priority_queue<tuple<long long, int, int, int>, vector<tuple<long long, int, int, int>>, greater<tuple<long long, int, int, int>>>Q;
	dist[0][0][0] = 0; Q.push(make_tuple(0, 0, 0, 0));

	while (!Q.empty()) {
		tuple<long long, int, int, int> tup = Q.top(); Q.pop();
		int px = get<1>(tup), py = get<2>(tup), mask = get<3>(tup);

		int sx[4] = { 0, 1, 0, -1 }, sy[4] = { 1, 0, -1,0 };
		for (int i = 0; i < 4; i++) {
			int tx = px + sx[i], ty = py + sy[i];
			if (tx < 0 || ty < 0 || tx > H || ty > W) continue;
			int mask1 = (mask ^ cp[px][py][i]);
			long long cost = cq[px][py][i];

			if (dist[tx][ty][mask1] > dist[px][py][mask] + cost) {
				dist[tx][ty][mask1] = dist[px][py][mask] + cost;
				Q.push(make_tuple(dist[tx][ty][mask1], tx, ty, mask1));
			}
		}
	}

	cout << dist[0][0][(1 << L.size()) - 1] << endl;
	return 0;
}

Compilation message (stderr)

wall.cpp: In function 'int main()':
wall.cpp:28:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int k = 0; k < L.size(); k++) {
                    ~~^~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40