Submission #1281364

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281364		arashmemar	Virus Experiment (JOI19_virus)	C++20	6 / 100	2093 ms	4388 KiB

virus

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

const int maxn = 1e3, maxm = 1e5 + 100;

int u[maxn][maxn], mn = maxn * maxn, cur;
bool ac[maxn][maxn], ad[maxm];

vector <pair <int, int>> d;

int st[16];

int conv(char c)
{
	if (c == 'N')
	{
		return 8;
	}
	if (c == 'E')
	{
		return 4;
	}
	if (c == 'S')
	{
		return 2;
	}
	return 1;
}

int get(int i, int j)
{
	int ret = 0;
	if (u[i][j] == 0)
	{
		return ret;
	}
	if (ac[i - 1][j])
	{
		ret += 8;
	}
	if (ac[i][j + 1])
	{
		ret += 4;
	}
	if (ac[i + 1][j])
	{
		ret += 2;
	}
	if (ac[i][j - 1])
	{
		ret += 1;
	}
	return ret;
}

int f(int i, int j)
{
	cur++;
	ac[i][j] = 1;
	d.push_back({i, j});
	if (cur > mn)
	{
		return maxn * maxn;
	}
	int ret = 1;
	if (ac[i - 1][j] == 0 and u[i - 1][j] and st[get(i - 1, j)] >= u[i - 1][j])
	{
		ret += f(i - 1, j);
	}
	if (cur > mn)
	{
		return maxn * maxn;
	}
	if (ac[i + 1][j] == 0 and u[i + 1][j] and st[get(i + 1, j)] >= u[i + 1][j])
	{
		ret += f(i + 1, j);
	}
	if (cur > mn)
	{
		return maxn * maxn;
	}
	if (ac[i][j - 1] == 0 and u[i][j - 1] and st[get(i, j - 1)] >= u[i][j - 1])
	{
		ret += f(i, j - 1);
	}
	if (cur > mn)
	{
		return maxn * maxn;
	}
	if (ac[i][j + 1] == 0 and u[i][j + 1] and st[get(i, j + 1)] >= u[i][j + 1])
	{
		ret += f(i, j + 1);
	}
	if (cur > mn)
	{
		return maxn * maxn;
	}
	return ret;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int m, r, c;
	cin >> m >> r >> c;

	string s;
	cin >> s;

	for (int N = 0;N < 2;N++)
	{
		for (int E = 0;E < 2;E++)
		{
			for (int S = 0;S < 2;S++)
			{
				for (int W = 0;W < 2;W++)
				{
					int cur = 8 * N + 4 * E + 2 * S + 1 * W;
					for (int i = 0;i < m;i++)
					{
						ad[i] = (cur & conv(s[i]));
					}
					int s = 0, mx = 0;
					for (int i = 0;i < m;i++)
					{
						if (ad[i])
						{
							s++;
						}
						else
						{
							mx = max(mx, s);
							s = 0;
						}
					}
					for (int i = 0;i < m;i++)
					{
						if (ad[i])
						{
							s++;
						}
						else
						{
							mx = max(mx, s);
							s = 0;
						}
					}
					mx = max(mx, s);
					if (mx == 2 * m)
					{
						mx = maxm;
					}
					st[cur] = mx;
				}
			}
		}
	}

	for (int i = 1;i <= r;i++)
	{
		for (int j = 1;j <= c;j++)
		{
			cin >> u[i][j];
		}
	}

	int ans = 1;

	for (int i = 1;i <= r;i++)
	{
		for (int j = 1;j <= c;j++)
		{
			if (u[i][j] == 0)
			{
				continue;
			}
			for (auto o : d)
			{
				ac[o.first][o.second] = 0;
			}
			d.clear();
			cur = 0;
			int ret = f(i, j);
			if (ret == mn)
			{
				ans++;
			}
			if (ret < mn)
			{
				mn = ret;
				ans = 1;
			}
		}
	}
	cout << mn << '\n' << ans;
}

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