Submission #1106238

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106238		cot7302	Nautilus (BOI19_nautilus)	C++17	100 / 100	146 ms	584 KiB

nautilus

#pragma GCC optimize("O2")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt")
#include <bits/stdc++.h>
#define ALL(X) begin(X), end(X)
using namespace std;
using i64 = long long;

template <class T>
using vec = vector<T>;

template <class T>
istream& operator>>(istream& is, vec<T>& V) {
    for (auto& x : V) is >> x;
    return is;
}

constexpr int kN = 500;

bitset<kN> dp[2][kN + 2], mask[kN + 1];

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int R, C, M; cin >> R >> C >> M;
    for (int i = 0; i < R; i++) {
        string S; cin >> S;
        for (int j = 0; j < C; j++)
            mask[i + 1][j] = dp[1][i + 1][j] = (S[j] == '.');
    }
    string op; cin >> op;
    for (int t = 0; t < M; t++) {
        const char c = op[t];
        for (int i = 0; i < R; i++) {
            if (c == '?') {
                dp[t & 1][i + 1] = mask[i + 1] & 
                                    (dp[!(t & 1)][i] | dp[!(t & 1)][i + 2] |
                                    (dp[!(t & 1)][i + 1] << 1) | (dp[!(t & 1)][i + 1] >> 1));
            }
            else if (c == 'N')
                dp[t & 1][i + 1] = mask[i + 1] & dp[!(t & 1)][i + 2];
            else if (c == 'S')
                dp[t & 1][i + 1] = mask[i + 1] & dp[!(t & 1)][i];
            else if (c == 'W')
                dp[t & 1][i + 1] = mask[i + 1] & (dp[!(t & 1)][i + 1] >> 1);
            else if (c == 'E')
                dp[t & 1][i + 1] = mask[i + 1] & (dp[!(t & 1)][i + 1] << 1);
        }
    }
    int ans{};
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++)
            ans += dp[!(M & 1)][i + 1][j];
    cout << ans << '\n';
}

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