Submission #1037033

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037033		ArthuroWich	Nautilus (BOI19_nautilus)	C++17	100 / 100	277 ms	1144 KiB

nautilus

#include <bits/stdc++.h>
using namespace std;
int r, c, m;
bitset<505> dpx[2][505], dpy[2][505], validx[505], validy[505], zero; // row, column
char grid[505][505];
bool isvalid(int i, int j) {
    return !(i < 0 || j < 0 || i >= r || j >= c);
}
void solve() {
    string s;
    cin >> r >> c >> m; 
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> grid[i][j];
            if (grid[i][j] != '#') {
                dpx[0][i][j] = validx[i][j] = 1; 
                dpy[0][j][i] = validy[j][i] = 1;
            }
        }
    }
    cin >> s;
    for (int i = 0; i < m; i++) {
        for (int x = 0; x < r; x++) {
            if (isvalid(x-1, 0) && (s[i] == 'N' || s[i] == '?')) {
                dpx[1][x-1] |= dpx[0][x];
            }
            if (isvalid(x+1, 0) && (s[i] == 'S' || s[i] == '?')) {
                dpx[1][x+1] |= dpx[0][x];
            }
            if (isvalid(0, 0) && (s[i] == 'W' || s[i] == '?')) {
                dpx[1][x] |= (dpx[0][x]>>1);
            }
            if (isvalid(0, 0) && (s[i] == 'E' || s[i] == '?')) {
                dpx[1][x] |= (dpx[0][x]<<1);
            }
        }
        for (int y = 0; y < c; y++) {
            if (isvalid(0, 0) && (s[i] == 'N' || s[i] == '?')) {
                dpy[1][y] |= (dpy[0][y]>>1);
            }
            if (isvalid(0, 0) && (s[i] == 'S' || s[i] == '?')) {
                dpy[1][y] |= (dpy[0][y]<<1);
            }
            if (isvalid(0, y-1) && (s[i] == 'W' || s[i] == '?')) {
                dpy[1][y-1] |= dpy[0][y];
            }
            if (isvalid(0, y+1) && (s[i] == 'E' || s[i] == '?')) {
                dpy[1][y+1] |= dpy[0][y];
            }
        }
        for (int x = 0; x < r; x++) {
            dpx[1][x] &= validx[x];
            dpx[0][x] = dpx[1][x];
            dpx[1][x] &= zero; 
        }
        for (int y = 0; y < c; y++) {
            dpy[1][y] &= validy[y]; 
            dpy[0][y] = dpy[1][y];
            dpy[1][y] &= zero;
        }
    }
    int ans = 0;
    for (int x = 0; x < r; x++) {
        for (int y = 0; y < c; y++) {
            if (dpx[0][x][y] || dpy[0][y][x]) {
                ans++;
            }
        }
    }
    cout << ans << endl;
}
int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    t = 1;
    while(t--) {
        solve();
    }
}

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