Submission #959690

#	Time	Username	Problem	Language	Result	Execution time	Memory
959690		Blagoj	Nautilus (BOI19_nautilus)	C++17	100 / 100	119 ms	824 KiB

nautilus

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) (x).begin(), (x).end()

const int mxn = 510;

bitset<mxn> dp[mxn][2], v[mxn];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < m; j++) v[i][j] = (s[j] == '.');
    }
    for (int i = 0; i < n; i++) dp[i][0] = v[i];
    string s;
    cin >> s;
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < n; j++) dp[j][1] = dp[j][0];
        if (s[i] == 'N') {
            dp[n - 1][0] = 0;
            for (int j = 0; j < n - 1; j++) dp[j][0] = dp[j + 1][1];
        }
        if (s[i] == 'E') {
            for (int j = 0; j < n; j++) dp[j][0] = (dp[j][1] << 1);
        }
        if (s[i] == 'S') {
            dp[0][0] = 0; 
            for (int j = 1; j < n; j++) dp[j][0] = dp[j - 1][1];
        }
        if (s[i] == 'W') {
            for (int j = 0; j < n; j++) dp[j][0] = (dp[j][1] >> 1);
        }
        if (s[i] == '?') {
            dp[n - 1][0] = 0;
            for (int j = 0; j < n - 1; j++) dp[j][0] = dp[j + 1][1];
            for (int j = 0; j < n; j++) dp[j][0] |= (dp[j][1] << 1);
            for (int j = 1; j < n; j++) dp[j][0] |= dp[j - 1][1];
            for (int j = 0; j < n; j++) dp[j][0] |= (dp[j][1] >> 1);
        }
        for (int j = 0; j < n; j++) dp[j][0] &= v[j];
    }
    int ans = 0;
    for (int i = 0; i < n; i++) ans += dp[i][0].count();
    cout << ans; 
}

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