Submission #643701

#	Time	Username	Problem	Language	Result	Execution time	Memory
643701		ParsaS	Nautilus (BOI19_nautilus)	C++14	100 / 100	539 ms	158748 KiB

nautilus

// In the name of God
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
typedef long long ll;
const int N = 500 + 5, MOD = 1e9 + 7;
bitset<N> grid[N], mtc[N][N * 10];

void solve() {
    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++)
            grid[i][j] = s[j] == '.';
    }
    string s; cin >> s;
    for (int i = 0; i < n; i++) {
        mtc[i][0] = grid[i];
    }
    bitset<N> null = 0;
    s = '.' + s;

    for (int i = 1; i <= k; i++) {
        for (int ip = 0; ip < n; ip++) {
            if (s[i] == 'S' || s[i] == '?') {
                mtc[ip][i] = mtc[ip][i] | ((ip ? mtc[ip - 1][i - 1] : null) & grid[ip]);
            }
            if (s[i] == 'N' || s[i] == '?') {
                mtc[ip][i] = mtc[ip][i] | (mtc[ip + 1][i - 1] & grid[ip]);
            }
            if (s[i] == 'E' || s[i] == '?')
                mtc[ip][i] = (grid[ip] & (mtc[ip][i - 1] << 1)) | mtc[ip][i];
            if (s[i] == 'W' || s[i] == '?')
                mtc[ip][i] = mtc[ip][i] | (grid[ip] & (mtc[ip][i - 1] >> 1));
        }

    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans += mtc[i][k].count();
    }
    cout << ans << endl;
}

int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();

    return 0;
}

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