Submission #1156994

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156994		htphong0909	Nautilus (BOI19_nautilus)	C++20	66 / 100	1096 ms	18888 KiB

nautilus

#include<bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
using namespace std;

int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, 1, 0, -1 };

bitset<1250250001> DP;
int n, m, h;

inline int ch(const int& a, const  int& b, const  int& c) {
    return (a - 1) * m + b + c * n * m;
}

char arr[501][501];

inline bool in(const int& x, const int& y) {
    return x > 0 && x <= n && y > 0 && y <= m && arr[x][y] == '.';
}

pair<int, int> di[101];

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    queue<array<int, 3>> q;
    cin >> n >> m >> h;
    di['N' - 'A'] = make_pair(-1, 0);
    di['S' - 'A'] = make_pair(1, 0);
    di['W' - 'A'] = make_pair(0, -1);
    di['E' - 'A'] = make_pair(0, 1);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == '.') {
                DP[ch(i, j, 0)] = true;
            }
        }
    }
    string s;
    cin >> s;
    s = '.' + s;
    for (int k = 1; k <= h; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (arr[i][j] != '.') continue;
                if (s[k] == '?') {
                    for (int t = 0; t < 4; t++) {
                        int x = i - dx[t];
                        int y = j - dy[t];
                        if (in(x, y) && DP[ch(x, y, k - 1)]) DP[ch(i, j, k)] = true;
                    }
                }
                else {
                    int x = i - di[s[k] - 'A'].first;
                    int y = j - di[s[k] - 'A'].second;
                    if (in(x, y) && DP[ch(x, y, k - 1)]) DP[ch(i, j, k)] = true;
                }
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            ans += DP[ch(i, j, h)];
        }
        cout << endl;
    }
    cout << ans;
    return 0;
}

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