Submission #485923

#	Time	Username	Problem	Language	Result	Execution time	Memory
485923		wmch13	Nautilus (BOI19_nautilus)	C++14	100 / 100	280 ms	157504 KiB

nautilus

#include <bits/stdc++.h>

using namespace std;

const int N = 5e2 + 9;
const int M = 5e3 + 9;

bitset <N> dp[N][M], good[N];

int main () {
	int r, c, m;
	cin >> r >> c >> m;
	
	for (int i = 1; i <= r; i++) {
		for (int j = c; j >= 1; j--) {
			char x;
			cin >> x;
			
			dp[i][0][j] = good[i][j] = (x == '.');
		}
	}
	
	string s;
	cin >> s;
	s = "#" + s;
	
	for (int t = 1; t <= m; t++) {
		for (int i = 1; i <= r; i++) {
			if (s[t] == 'N') 
				dp[i][t] = dp[i + 1][t - 1] & good[i];
			
			if (s[t] == 'W')
				dp[i][t] = (dp[i][t - 1] << 1) & good[i];
				
			if (s[t] == '?')
				dp[i][t] = (dp[i + 1][t - 1] | dp[i - 1][t - 1] | (dp[i][t - 1] << 1) | (dp[i][t - 1] >> 1)) & good[i];
		
			if (s[t] == 'S')
				dp[i][t] = dp[i - 1][t - 1] & good[i];
				
			if (s[t] == 'E')
				dp[i][t] = (dp[i][t - 1] >> 1) & good[i];
				
		}
	}
	
	int res = 0;
	for (int i = 1; i <= r; i++)
		res += dp[i][m].count();
	
	cout << res << "\n";
	return 0;
}

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