Submission #832944

#	Time	Username	Problem	Language	Result	Execution time	Memory
832944		serifefedartar	Nautilus (BOI19_nautilus)	C++17	100 / 100	263 ms	157660 KiB

nautilus

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 1000000007
#define LOGN 20
#define MAXN 300005

int main() {
	fast
	int R, C, M;
	cin >> R >> C >> M;

	vector<bitset<505>> sea(R);
	bitset<505> dp[R+1][M+1];
	for (int i = 0; i < R; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < C; j++) {
			if (s[j] == '.')
				sea[i][j] = 1;
		}
	}

	bitset<505> temp;
	string way;
	cin >> way;
	for (int i = 0; i < R; i++)
		dp[i][0] = sea[i];

	for (int step = 0; step < M; step++) {
		for (int row = 0; row < R; row++) {
			if (way[step] == 'W')
				dp[row][step+1] = dp[row][step] >> 1;
			else if (way[step] == 'E')
				dp[row][step+1] = dp[row][step] << 1;
			else if (way[step] == 'N')
				dp[row][step+1] = dp[row+1][step];
			else if (way[step] == 'S') {
				if (row == 0)
					dp[row][step+1] = temp;
				else
					dp[row][step+1] = dp[row-1][step];
			} else {
				dp[row][step+1] = (dp[row][step] << 1) | (dp[row][step] >> 1) | (dp[row+1][step]);
				if (row != 0)
					dp[row][step+1] = (dp[row][step+1] | dp[row-1][step]);
			}
			dp[row][step+1] = (dp[row][step+1] & sea[row]);
		}
	}

	int ans = 0;
	for (int i = 0; i < R; i++)
		ans += dp[i][M].count();
	cout << ans << "\n";
}

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