Submission #313744

#	Time	Username	Problem	Language	Result	Execution time	Memory
313744		sofapuden	Nautilus (BOI19_nautilus)	C++14	100 / 100	197 ms	764 KiB

nautilus

#include <bits/stdc++.h>

using namespace std;

const int maxn = 505;

bitset<maxn> G[maxn], dp[maxn][2];
int n, m, Q;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m >> Q;
	for(int i = 1; i <= n; ++i){
		for(int j = 0; j < m; ++j){
			char c; cin >> c;
			G[i][j] = (c == '.');
		}
		dp[i][0] = G[i];
	}
	string s; cin >> s;
	for(int i = 0; i < Q; ++i){
		for(int j = 1; j <= n; ++j){
			if(s[i] == '?')dp[j][(i+1)&1] = dp[j+1][i&1] | dp[j-1][i&1] | (dp[j][i&1]<<1) | (dp[j][i&1] >> 1);
			if(s[i] == 'N')dp[j][(i+1)&1] = dp[j+1][i&1];
			if(s[i] == 'E')dp[j][(i+1)&1] = dp[j][i&1]<<1;
			if(s[i] == 'W')dp[j][(i+1)&1] = dp[j][i&1]>>1;
			if(s[i] == 'S')dp[j][(i+1)&1] = dp[j-1][i&1];
			dp[j][(i+1)&1]&=G[j];
		}
	}
	int ans = 0;
	for(int i = 1; i <= n; ++i){
		ans+=dp[i][Q&1].count();
	} 
	cout << ans << "\n";
}
			
					
	

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