Submission #667175

#	Time	Username	Problem	Language	Result	Execution time	Memory
667175		Kahou	Nautilus (BOI19_nautilus)	C++14	100 / 100	291 ms	156744 KiB

nautilus

#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int N = 505, M = 5005;
int n, m, k;
string s;
bitset<N*N> grid;
bitset<N*N> dp[M];

char dr[4] = {'N','E','S','W'};
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

int f(int x, int y) {
	return x*N + y;
}

void solve() {
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		for (int j= 1; j <= m; j++) {
			char c;
			cin >> c;
			grid[f(i, j)] = dp[0][f(i,j)] = (c == '.');
		}
	}
	cin >> s;
	for (int p = 1; p <= k; p++) {
		for (int i = 0; i < 4; i++) {
			if (s[p-1] == '?' || s[p-1] == dr[i]) {
				int off = f(dx[i], dy[i]);
				if (off >= 0) dp[p] = dp[p]|(dp[p-1]<<off);
				else dp[p] = dp[p]|(dp[p-1]>>(-off));
			}
		}
		dp[p] = dp[p] & grid;
	}
	cout << dp[k].count() << endl;
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solve();
	return 0;
}

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