Submission #544670

#	Time	Username	Problem	Language	Result	Execution time	Memory
544670		pokmui9909	물탱크 (KOI18_watertank)	C++17	100 / 100	523 ms	44060 KiB

watertank

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

int N, M, H;
int A[1005][1005][5];
int W[1005][1005];
int xdir[4] = { -1, 0, 1, 0 };
int ydir[4] = { 0, 1, 0, -1 };

struct info
{
	int x, y, h;
};

struct cmp
{
	bool operator()(info a, info b)
	{
		return a.h > b.h;
	}
};

priority_queue<info, vector<info>, cmp> pq;

signed main()
{
	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(false);

	cin >> N >> M >> H;
	for (int i = 1; i <= N + 1; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			int K; cin >> K;
			A[i - 1][j][2] = A[i][j][0] = K;
		}
	}
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M + 1; j++)
		{
			int K; cin >> K;
			A[i][j - 1][1] = A[i][j][3] = K;
		}
	}
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
			W[i][j] = H;
	}
	for (int i = 1; i <= M; i++)
	{
		if (A[1][i][0] != -1 && W[1][i] >= A[1][i][0])
		{
			W[1][i] = A[1][i][0];
			pq.push({ 1, i, A[1][i][0] });
		}
		if (A[N][i][2] != -1 && W[N][i] >= A[N][i][2])
		{ 
			W[N][i] = A[N][i][2]; 
			pq.push({ N, i, A[N][i][2] }); 
		}
	}
	for (int i = 1; i <= N; i++)
	{
		if (A[i][1][3] != -1 && W[i][1] >= A[i][1][3])
		{ 
			W[i][1] = A[i][1][3];
			pq.push({ i, 1, A[i][1][3] }); 
		}
		if (A[i][M][1] != -1 && W[i][M] >= A[i][M][1])
		{ 
			W[i][M] = A[i][M][1]; 
			pq.push({ i, M, A[i][M][1] });
		}
	}
	while (!pq.empty())
	{
		int x = pq.top().x, y = pq.top().y, h = pq.top().h; pq.pop();
		if (h != W[x][y]) continue;
		for (int i = 0; i < 4; i++)
		{
			if (A[x][y][i] == -1) continue;
			int nx = x + xdir[i], ny = y + ydir[i];
			if (nx < 1 || nx > N || ny < 1 || ny > M) continue;
			int nh = max(min(A[x][y][i], W[nx][ny]), W[x][y]);
			if (W[nx][ny] <= nh) continue;
			W[nx][ny] = nh;
			pq.push({ nx, ny, nh });
		}
	}
	int ans = 0;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
			ans += W[i][j];
	}
	cout << ans;
}

• Subtask 1: 6 / 6
• Subtask 2: 18 / 18
• Subtask 3: 15 / 15
• Subtask 4: 21 / 21
• Subtask 5: 40 / 40