Submission #1183954

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183954		crafticat	Nautilus (BOI19_nautilus)	C++20	66 / 100	1095 ms	580 KiB

nautilus

#include <iostream>
#include <vector>
#include <vector>
using namespace std;


#define F0R(i, n) for (int i = 0; i < n;i++)
#define FOR(i, j , n) for (int i = j ; i< n;i++)

template<typename T>
using V = vector<T>;
using vi = V<int>;
using pi = pair<int,int>;

V<pi> getDirections(char c) {
    if (c == 'N') {
        return {{0,-1}};
    }
    if (c == 'E') {
        return {{1,0}};
    }
    if (c == 'S') {
        return {{0,1}};
    }
    if (c == 'W') {
        return {{-1,0}};
    }

    if (c == '?') {
        return {{1,0}, {0,1}, {-1,0}, {0, -1}};
    }

    exit(5);
}

int main() {
    int r, c, m; cin >> r >> c >> m;
    vector<vector<bool>> temp((r + 2), vector<bool>(c + 2, false));

    F0R(i, r) {
        F0R(j, c) {
            char ch; cin >> ch;
            temp[i + 1][j + 1] = ch == '#';
        }
    }

    vector<vector<bool>> dp((r + 2), vector<bool>(c + 2, true));
    FOR(i, 1, r + 1) {
        FOR(j, 1, c + 1) {
            if (temp[i][j]) dp[i][j] = false;
        }
    }

    string s; cin >> s;

    F0R(i, m) {
        vector<vector<bool>> newDp((r + 2), vector<bool>(c + 2, false));

        FOR(j, 1, r + 1) {
            FOR(k, 1, c + 1) {
                for (auto [dy, dx] : getDirections(s[i])) {
                    if (dp[j][k] && !temp[j + dx][k + dy]) newDp[j + dx][k + dy] = 1;
                }
            }
        }
        dp = newDp;
    }

    int ans = 0;
    F0R(i, r) {
        F0R(j, c) {
            ans += dp[i + 1][j + 1];
        }
    }
    cout << ans << endl;
}

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