Submission #477502

#	Time	Username	Problem	Language	Result	Execution time	Memory
477502		Sohsoh84	Nautilus (BOI19_nautilus)	C++17	100 / 100	245 ms	900 KiB

nautilus

// ¯\_(ツ)_/¯
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> pll;
 
#define all(x)                      (x).begin(),(x).end()
#define X                           first
#define Y                           second
#define sep                         ' '
#define endl                        '\n'
#define debug(x)                    cerr << #x << ": " <<  x << endl;
 
const ll MAXN = 500 + 3;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; // 998244353; // 1e9 + 9;
 
int n, m, l;
bitset<MAXN * MAXN> dp[MAXN], G, W, E;
string s;
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m >> l;
 
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			char c;
			cin >> c;
			G[i * m + j] = (c == '.');
			W[i * m + j] = E[i * m + j] = true;
		}
 
		W[i * m + m - 1] = false;
		E[i * m] = false;
	}
 
	cin >> s;
	s = "." + s;
	dp[0] = G;
	
	for (int i = 1; i <= l; i++) {
		int ind = i & 1;
		dp[ind].reset();
 
		if (s[i] == 'N' || s[i] == '?') dp[ind] |= (dp[1 - ind] >> m);
		if (s[i] == 'S' || s[i] == '?') dp[ind] |= (dp[1 - ind] << m);
		if (s[i] == 'E' || s[i] == '?') dp[ind] |= ((dp[1 - ind] << 1) & E);
		if (s[i] == 'W' || s[i] == '?') dp[ind] |= ((dp[1 - ind] >> 1) & W);
		dp[ind] &= G;
	}
 
	cout << dp[l & 1].count() << endl;
	return 0;
}

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