Submission #565234

#	Time	Username	Problem	Language	Result	Execution time	Memory
565234		hoanghq2004	Nautilus (BOI19_nautilus)	C++14	100 / 100	299 ms	157496 KiB

nautilus

#include <bits/stdc++.h>

using namespace std;

int n, m, k;
bitset <510> dp[510][5010], a[510];
int res;

int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n >> m >> k;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            char c;
            cin >> c;
            a[i][j] = (c == '.');
        }
    }
    string s;
    cin >> s;
    for (int i = 1; i <= n; ++i) dp[i][0] = a[i];
    for (int t = 1; t <= k; ++t) {
        for (int i = 1; i <= n; ++i) {
            if (s[t - 1] == 'N') dp[i][t] = dp[i + 1][t - 1] & a[i];
            if (s[t - 1] == 'S') dp[i][t] = dp[i - 1][t - 1] & a[i];
            if (s[t - 1] == 'W') dp[i][t] = (dp[i][t - 1] >> 1) & a[i];
            if (s[t - 1] == 'E') dp[i][t] = (dp[i][t - 1] << 1) & a[i];
            if (s[t - 1] == '?')
                dp[i][t] = (dp[i + 1][t - 1] & a[i]) | (dp[i - 1][t - 1] & a[i]) | ((dp[i][t - 1] >> 1) & a[i]) | ((dp[i][t - 1] << 1) & a[i]);
        }
    }
    for (int i = 1; i <= n; ++i) res += dp[i][k].count();
    cout << res;
}

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