Submission #584785

#	Time	Username	Problem	Language	Result	Execution time	Memory
584785		penguinhacker	Nautilus (BOI19_nautilus)	C++17	100 / 100	85 ms	668 KiB

nautilus

#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("Ofast")

#define ll long long
#define ar array
 
const int mxN=500;
int n, m, q;
bitset<mxN> mask[mxN], dp[mxN];
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> q;
	for (int i=0; i<n; ++i) {
		string s;
		cin >> s;
		for (int j=0; j<m; ++j)
			if (s[j]=='.')
				mask[i][j]=1, dp[i][j]=1;
	}
	string query;
	cin >> query;
	for (char c : query) {
		bitset<mxN> ndp[mxN];
		if (c=='W'||c=='?')
			for (int i=0; i<n; ++i)
				ndp[i]|=(dp[i]>>1)&mask[i];
		if (c=='E'||c=='?')
			for (int i=0; i<n; ++i)
				ndp[i]|=(dp[i]<<1)&mask[i];
		if (c=='N'||c=='?')
			for (int i=1; i<n; ++i)
				ndp[i-1]|=dp[i]&mask[i-1];
		if (c=='S'||c=='?')
			for (int i=0; i+1<n; ++i)
				ndp[i+1]|=dp[i]&mask[i+1];
		for (int i=0; i<n; ++i)
			swap(dp[i], ndp[i]);
	}
	int ans=0;
	for (int i=0; i<n; ++i)
		ans+=dp[i].count();
	cout << ans;
	return 0;
}

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