# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
646577 | 2022-09-30T07:49:41 Z | alextodoran | Nautilus (BOI19_nautilus) | C++17 | 126 ms | 728 KB |
/** ____ ____ ____ ____ ____ ||a |||t |||o |||d |||o || ||__|||__|||__|||__|||__|| |/__\|/__\|/__\|/__\|/__\| **/ #include <bits/stdc++.h> using namespace std; typedef long long ll; int main () { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int N, M, K; cin >> N >> M >> K; bitset <500> sea[N]; for (int i = 0; i < N; i++) { string row; cin >> row; for (int j = 0; j < M; j++) { sea[i][j] = (row[j] == '.'); } } bitset <500> dp[2][N]; for (int i = 0; i < N; i++) { dp[0][i] = sea[i]; } string path; cin >> path; for (int k = 1; k <= K; k++) { if (path[k - 1] == '?') { for (int i = 0; i < N; i++) { dp[k & 1][i] = ((dp[(k - 1) & 1][i] >> 1) | (dp[(k - 1) & 1][i] << 1)); if (i > 0) { dp[k & 1][i] |= dp[(k - 1) & 1][i - 1]; } if (i < N - 1) { dp[k & 1][i] |= dp[(k - 1) & 1][i + 1]; } } } else { int di = 0, dj = 0; if (path[k - 1] == 'N') { dp[k & 1][N - 1].reset(); for (int i = 0; i < N - 1; i++) { dp[k & 1][i] = dp[(k - 1) & 1][i + 1]; } } else if (path[k - 1] == 'E') { for (int i = 0; i < N; i++) { dp[k & 1][i] = (dp[(k - 1) & 1][i] << 1); } } else if (path[k - 1] == 'S') { dp[k & 1][0].reset(); for (int i = 1; i < N; i++) { dp[k & 1][i] = dp[(k - 1) & 1][i - 1]; } } else { for (int i = 0; i < N; i++) { dp[k & 1][i] = (dp[(k - 1) & 1][i] >> 1); } } } for (int i = 0; i < N; i++) { dp[k & 1][i] &= sea[i]; } } int answer = 0; for (int i = 0; i < N; i++) { answer += dp[K & 1][i].count(); } cout << answer << "\n"; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 340 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 340 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
7 | Correct | 1 ms | 340 KB | Output is correct |
8 | Correct | 1 ms | 328 KB | Output is correct |
9 | Correct | 1 ms | 340 KB | Output is correct |
10 | Correct | 1 ms | 340 KB | Output is correct |
11 | Correct | 1 ms | 340 KB | Output is correct |
12 | Correct | 1 ms | 340 KB | Output is correct |
13 | Correct | 1 ms | 340 KB | Output is correct |
14 | Correct | 1 ms | 340 KB | Output is correct |
15 | Correct | 1 ms | 340 KB | Output is correct |
16 | Correct | 1 ms | 324 KB | Output is correct |
17 | Correct | 1 ms | 340 KB | Output is correct |
18 | Correct | 1 ms | 340 KB | Output is correct |
19 | Correct | 2 ms | 340 KB | Output is correct |
20 | Correct | 1 ms | 324 KB | Output is correct |
21 | Correct | 1 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 340 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
7 | Correct | 1 ms | 340 KB | Output is correct |
8 | Correct | 1 ms | 328 KB | Output is correct |
9 | Correct | 1 ms | 340 KB | Output is correct |
10 | Correct | 1 ms | 340 KB | Output is correct |
11 | Correct | 1 ms | 340 KB | Output is correct |
12 | Correct | 1 ms | 340 KB | Output is correct |
13 | Correct | 1 ms | 340 KB | Output is correct |
14 | Correct | 1 ms | 340 KB | Output is correct |
15 | Correct | 1 ms | 340 KB | Output is correct |
16 | Correct | 1 ms | 324 KB | Output is correct |
17 | Correct | 1 ms | 340 KB | Output is correct |
18 | Correct | 1 ms | 340 KB | Output is correct |
19 | Correct | 2 ms | 340 KB | Output is correct |
20 | Correct | 1 ms | 324 KB | Output is correct |
21 | Correct | 1 ms | 340 KB | Output is correct |
22 | Correct | 62 ms | 680 KB | Output is correct |
23 | Correct | 62 ms | 596 KB | Output is correct |
24 | Correct | 60 ms | 668 KB | Output is correct |
25 | Correct | 63 ms | 668 KB | Output is correct |
26 | Correct | 59 ms | 584 KB | Output is correct |
27 | Correct | 95 ms | 728 KB | Output is correct |
28 | Correct | 95 ms | 664 KB | Output is correct |
29 | Correct | 93 ms | 672 KB | Output is correct |
30 | Correct | 95 ms | 596 KB | Output is correct |
31 | Correct | 96 ms | 596 KB | Output is correct |
32 | Correct | 122 ms | 668 KB | Output is correct |
33 | Correct | 119 ms | 668 KB | Output is correct |
34 | Correct | 121 ms | 712 KB | Output is correct |
35 | Correct | 126 ms | 680 KB | Output is correct |
36 | Correct | 121 ms | 680 KB | Output is correct |