제출 #1287317

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1287317		am_aadvik	바이러스 (JOI19_virus)	C++20	20 / 100	336 ms	12232 KiB

virus

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int c(char i) { return ((i == 'N') ? 0 : ((i == 'E') ? 1 : ((i == 'W') ? 2 : 3))); }
int di[] = { 1, 0, 0, -1 };
int dj[] = { 0, -1, 1, 0 };
bool check(int i, int j, vector<vector<int>>& vis, int n, int m, vector<int> mx, int val) {
	int mask = 0;
	for (int d = 0; d < 4; ++d) {
		int ni = di[d] + i, nj = dj[d] + j;
		if ((ni < 0) || (nj < 0) || (nj >= m) || (ni >= n)) continue;
		if (vis[ni][nj]) mask |= (1 << (3 - d));
	}
	return mx[mask] >= val;
}
int main() {
	int k, n, m; cin >> k >> n >> m;
	string s; cin >> s; s += s, k += k;
	vector<vector<int>> a(n, vector<int>(m));
	for (auto& x : a) for (auto& y : x) cin >> y;
	for (auto& x : a) for (auto& y : x) y = ((y == 0) ? 1e9 : y);
	vector<int> mx(20);
	for (int j = 0; j < 16; ++j) {
		for (int i = 0; i < k; ++i) {
			int cur = 0;
			while ((i < k) && (j & (1 << c(s[i])))) ++i, ++cur;
			mx[j] = max(mx[j], cur);
		}
	}
	for (int i = 0; i < 20; ++i) 
		mx[i] += ((mx[i] == k) * 2e5);
	vector<int> res;
	if ((n * m) <= 2500) {
		vector<vector<int>> vis(n, vector<int>(m, 0));
		for (int i = 0; i < n; ++i)
			for (int j = 0; j < m; ++j) {
				if (a[i][j] == 1e9) continue;
				vis.assign(n, vector<int>(m, 0));
				queue<pair<int, int>> q;
				q.push({ i, j }), vis[i][j] = 1;
				while (!q.empty()) {
					auto f = q.front(); q.pop();
					int x = f.first, y = f.second;
					for (int d = 0; d < 4; ++d) {
						int ni = di[d] + x, nj = dj[d] + y;
						if ((ni < 0) || (nj < 0) || (nj >= m) || (ni >= n)) continue;
						if (vis[ni][nj]) continue;
						if (check(ni, nj, vis, n, m, mx, a[ni][nj])) 
							q.push({ ni, nj }), vis[ni][nj] = 1;
					}
				}
				int ans = 0;
				for (auto& x : vis) for (auto& y : x) ans += y;
				res.push_back(ans);
			}
	}
	else {
		vector<vector<int>> wmx(n, vector<int>(m, m - 1));
		vector<vector<int>> emx(n, vector<int>(m, 0));
		for(int i = 0; i < n; ++i)
			for (int j = 1; j < m; ++j)
				if (a[i][j - 1] > mx[2]) emx[i][j] = j;
				else emx[i][j] = emx[i][j - 1];
		for (int i = 0; i < n; ++i)
			for (int j = m - 2; j >= 0; --j)
				if (a[i][j + 1] > mx[4]) wmx[i][j] = j;
				else wmx[i][j] = wmx[i][j + 1];
		for (int i = 0; i < n; ++i)
			for (int j = 0; j < m; ++j)
				if(a[i][j] != 1e9)
					res.push_back(wmx[i][j] - emx[i][j] + 1);
	}
	int ans = 0;
	sort(res.begin(), res.end());
	for (auto x : res) ans += (x == res[0]);
	cout << res[0] << endl << ans;
}

• Subtask 1: 14 / 14
• Subtask 2: 6 / 6
• Subtask 3: 0 / 80