Submission #1187813

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187813		arazoglun	Nautilus (BOI19_nautilus)	C++20	100 / 100	981 ms	1056 KiB

nautilus

#pragma GCC optimize("Ofast")
#pragma GCC target("popcnt")
#include <bits/stdc++.h>
#define l1 long long
#define pi1 pair<int, int>
using namespace std;

const int N = 501;

int n, m, x;
char z[N*N*3];
char g[N][N];
bitset<N*N> dp, water;

#define pos(i, j) (i*N+j)

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> n >> m >> x;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> g[i][j];
            if (g[i][j] == '.')
                water[pos(i, j)] = 1;
        }
    }
    for (int i = 0; i < x; cin >> z[i++]);
    dp = water;
    for (const char &c : z) {
        if (c == '?') dp = (dp<<1) | (dp>>1) | (dp<<N) | (dp>>N);
        else if (c == 'E') dp = (dp<<1);
        else if (c == 'W') dp = (dp>>1);
        else if (c == 'S') dp = (dp<<N);
        else if (c == 'N') dp = (dp>>N);
        dp &= water;
    }
    cout << dp.count();
}

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