Submission #703569

#	Time	Username	Problem	Language	Result	Execution time	Memory
703569		bebra	Nautilus (BOI19_nautilus)	C++17	100 / 100	241 ms	159400 KiB

nautilus

#include <bits/stdc++.h>
using namespace std;

#define dbg(x) cerr << #x << ": " << x << endl;

const int MAX_N = 500 + 5;
const int MAX_M = 5000 + 5;
string a[MAX_N];

vector<pair<int, int>> delta = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
bitset<MAX_N> dp[MAX_M][MAX_N];
bitset<MAX_N> mask[MAX_N];


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, t;
    cin >> n >> m >> t;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        for (int j = 0; j < m; ++j) {
            if (a[i][j] == '.') {
                mask[i].set(j);
            }
        }
    }

    string s;
    cin >> s;
    reverse(s.begin(), s.end());

    vector<vector<pair<int, int>>> dir(t);
    for (int i = 0; i < t; ++i) {
        auto c = s[i];
        if (c == 'N') {
            dir[i] = {delta[0]};
        } else if (c == 'S') {
            dir[i] = {delta[1]};
        } else if (c == 'W') {
            dir[i] = {delta[2]};
        } else if (c == 'E') {
            dir[i] = {delta[3]};
        } else {
            dir[i] = delta;
        }
    }
    for (int i = 0; i < n; ++i) {
        dp[t][i] = mask[i];
    }
    // reverse the operations and check if there exists at least one starting position
    for (int k = t - 1; k >= 0; --k) {
        for (const auto& [di, dj] : dir[k])  {
            for (int i = 0; i < n; ++i) {
                if (i == 0 && di == -1) continue;
                if (dj >= 0) {
                    dp[k][i] |= (dp[k + 1][i + di] >> abs(dj)) & mask[i];
                } else {
                    dp[k][i] |= (dp[k + 1][i + di] << abs(dj)) & mask[i];
                }
            }
        }
    }

    int ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            ans += dp[0][i].test(j);
        }
    }

    cout << ans << '\n';

    
    return 0;
}

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