Submission #140686

#	Time	Username	Problem	Language	Result	Execution time	Memory
140686		Minnakhmetov	Nautilus (BOI19_nautilus)	C++14	100 / 100	213 ms	1064 KiB

nautilus

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

#define ll long long
#define all(aaa) aaa.begin(), aaa.end()

const int N = 505;
char s[N][N];
bitset<N> dp[2][N], water[N];

int r, c, m;

void horizontalShift(int i, int d) {
    for (int x = 0; x < r; x++) {
        if (d < 0) {
            dp[i ^ 1][x] |= dp[i][x] >> -d;
        }
        else {
            dp[i ^ 1][x] |= dp[i][x] << d;   
        }
    }
}

void verticalShift(int i, int d) {
    for (int x = 0; x < r; x++) {
        if (x + d >= 0 && x + d < r)
            dp[i ^ 1][x + d] |= dp[i][x];
    }
}

signed main() {
#ifdef HOME
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> r >> c >> m;

    for (int i = 0; i < r; i++) {
        cin >> s[i];
        for (int j = 0; j < c; j++) {
            if (s[i][j] == '.') {
                water[i][j] = 1;
                dp[0][i][j] = 1;
            }
        }
    }

    string s;
    cin >> s;

    for (int i = 0, j = 0; i < m; i++, j ^= 1) {
        for (int k = 0; k < r; k++) {
            dp[j ^ 1][k].reset();
        }

        if (s[i] == 'W') {
            horizontalShift(j, -1);
        }
        else if (s[i] == 'E') {
            horizontalShift(j, 1);
        }
        else if (s[i] == 'N') {
            verticalShift(j, -1);
        }
        else if (s[i] == 'S') {
            verticalShift(j, 1);
        }
        else {
            horizontalShift(j, 1);
            horizontalShift(j, -1);
            verticalShift(j, -1);
            verticalShift(j, 1);
        }

        for (int k = 0; k < r; k++) {
            dp[j ^ 1][k] &= water[k];
        }
    }

    int ans = 0;

    for (int i = 0; i < r; i++)
        ans += dp[m & 1][i].count();

    cout << ans;

    return 0;
}

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