oj.uz

답안 #703569

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
703569 2023-02-27T17:02:10 Z bebra Nautilus (BOI19_nautilus) C++17
100 / 100
 241 ms 159400 KB 
#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.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Correct 1 ms 1364 KB Output is correct
4 Correct 1 ms 1364 KB Output is correct
5 Correct 1 ms 1364 KB Output is correct
6 Correct 1 ms 1364 KB Output is correct

Subtask #2
37.0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Correct 1 ms 1364 KB Output is correct
4 Correct 1 ms 1364 KB Output is correct
5 Correct 1 ms 1364 KB Output is correct
6 Correct 1 ms 1364 KB Output is correct
7 Correct 1 ms 1380 KB Output is correct
8 Correct 1 ms 1364 KB Output is correct
9 Correct 1 ms 1364 KB Output is correct
10 Correct 1 ms 1364 KB Output is correct
11 Correct 1 ms 1364 KB Output is correct
12 Correct 1 ms 1364 KB Output is correct
13 Correct 1 ms 1364 KB Output is correct
14 Correct 2 ms 1364 KB Output is correct
15 Correct 1 ms 1364 KB Output is correct
16 Correct 1 ms 1364 KB Output is correct
17 Correct 1 ms 1364 KB Output is correct
18 Correct 1 ms 1364 KB Output is correct
19 Correct 1 ms 1364 KB Output is correct
20 Correct 2 ms 1364 KB Output is correct
21 Correct 1 ms 1364 KB Output is correct

Subtask #3
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Correct 1 ms 1364 KB Output is correct
4 Correct 1 ms 1364 KB Output is correct
5 Correct 1 ms 1364 KB Output is correct
6 Correct 1 ms 1364 KB Output is correct
7 Correct 1 ms 1380 KB Output is correct
8 Correct 1 ms 1364 KB Output is correct
9 Correct 1 ms 1364 KB Output is correct
10 Correct 1 ms 1364 KB Output is correct
11 Correct 1 ms 1364 KB Output is correct
12 Correct 1 ms 1364 KB Output is correct
13 Correct 1 ms 1364 KB Output is correct
14 Correct 2 ms 1364 KB Output is correct
15 Correct 1 ms 1364 KB Output is correct
16 Correct 1 ms 1364 KB Output is correct
17 Correct 1 ms 1364 KB Output is correct
18 Correct 1 ms 1364 KB Output is correct
19 Correct 1 ms 1364 KB Output is correct
20 Correct 2 ms 1364 KB Output is correct
21 Correct 1 ms 1364 KB Output is correct
22 Correct 146 ms 159048 KB Output is correct
23 Correct 160 ms 159324 KB Output is correct
24 Correct 143 ms 159280 KB Output is correct
25 Correct 138 ms 159220 KB Output is correct
26 Correct 142 ms 159316 KB Output is correct
27 Correct 188 ms 159308 KB Output is correct
28 Correct 191 ms 159236 KB Output is correct
29 Correct 193 ms 159312 KB Output is correct
30 Correct 193 ms 159280 KB Output is correct
31 Correct 187 ms 159360 KB Output is correct
32 Correct 227 ms 159372 KB Output is correct
33 Correct 228 ms 159336 KB Output is correct
34 Correct 241 ms 159328 KB Output is correct
35 Correct 233 ms 159400 KB Output is correct
36 Correct 226 ms 159352 KB Output is correct