Submission #900618

#	Time	Username	Problem	Language	Result	Execution time	Memory
900618		Valaki2	Nautilus (BOI19_nautilus)	C++14	100 / 100	125 ms	604 KiB

nautilus

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

const int bsz = (500 * 502);

const int maxn = 500;
const int maxk = 5000;

int n, m, k;
bitset<bsz> mask;
bitset<bsz> dp[2];

void solve() {
	cin >> n >> m >> k;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			char ch;
			cin >> ch;
			if(ch == '.') {
				mask[j + (i - 1) * (m + 2)] = 1;
			}
		}
	}
	dp[0] = mask;
	for(int i = 1; i <= k; i++) {
		char ch;
		cin >> ch;
		bitset<bsz> &cur = dp[i % 2];
		bitset<bsz> &prev = dp[1 - (i % 2)];
		if(ch == 'N') {
			cur = prev >> (m + 2);
		}
		if(ch == 'E') {
			cur = prev << 1;
		}
		if(ch == 'S') {
			cur = prev << (m + 2);
		}
		if(ch == 'W') {
			cur = prev >> 1;
		}
		if(ch == '?') {
			cur = prev >> (m + 2);
			cur |= prev << 1;
			cur |= prev << (m + 2);
			cur |= prev >> 1;
		}
		cur &= mask;
		/*for(int l = 1; l <= n; l++) {
			for(int j = 1; j <= m; j++) {
				cout << cur[j + (l - 1) * (m + 2)];
			}
			cout << "\n";
		}
		cout << "---\n";*/
	}
	cout << dp[k % 2].count() << "\n";
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
	int T = 1;
	//cin >> T;
	while(T--) {
		solve();
	}
}

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