Submission #332835

#	Time	Username	Problem	Language	Result	Execution time	Memory
332835		sinamhdv	Nautilus (BOI19_nautilus)	C++11	100 / 100	268 ms	160768 KiB

nautilus

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1000 * 1000 * 1000;
const ll LINF = (ll)INF * INF;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define msub(a, b) ((mod + ((a) - (b)) % mod) % mod)
#define mdiv(a, b) ((a) * poww((b), mod - 2) % mod)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define endl '\n'

#define MAXN 510
#define MAXM 5010

bitset<MAXN> dp[MAXM][MAXN];
char grid[MAXN][MAXN];
bitset<MAXN> gbit[MAXN];
char s[MAXM];
int r, c, m;

int32_t main(void)
{
	fast_io;
	cin >> r >> c >> m;
	FOR(i, 1, r + 1)
	{
		FOR(j, 1, c + 1)
		{
			cin >> grid[i][j];
		}
	}
	cin >> (s + 1);
	FOR(i, 1, r + 1)
	{
		FOR(j, 1, c + 1)
		{
			dp[0][i][j] = (grid[i][j] != '.');
			gbit[i][j] = (grid[i][j] != '.');
		}
		dp[0][i][0] = dp[0][i][c + 1] = 1;
	}
	FOR(k, 0, m + 1)
	{
		dp[k][r + 1].set();
		dp[k][0].set();
	}
	FOR(k, 1, m + 1)
	{
		FOR(i, 1, r + 1)
		{
			if (s[k] == 'N')
			{
				dp[k][i] |= dp[k - 1][i + 1];
			}
			else if (s[k] == 'S')
			{
				dp[k][i] |= dp[k - 1][i - 1];
			}
			else if (s[k] == 'E')
			{
				dp[k][i] |= (dp[k - 1][i] << 1);
			}
			else if (s[k] == 'W')
			{
				dp[k][i] |= (dp[k - 1][i] >> 1);
			}
			else	// ?
			{
				dp[k][i] |= (dp[k - 1][i] >> 1) & (dp[k - 1][i] << 1) & (dp[k - 1][i - 1]) & (dp[k - 1][i + 1]);
			}
			dp[k][i] |= gbit[i];
			dp[k][i][0] = dp[k][i][c + 1] = 1;
		}
		/*FOR(i, 1, r +1)
		{
			FOR(j, 1, c + 1)
			{
				cout << dp[k][i][j] << ' ';
			}
			cout << endl;
		}
		dbg("================");
		*/
	}
	int ans = 0;
	FOR(i, 1, r + 1)
	{
		FOR(j, 1, c + 1)
		{
			if (dp[m][i][j] == 0)
			{
				ans++;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

• Subtask 1: 29 / 29
• Subtask 2: 37 / 37
• Subtask 3: 34 / 34