# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
914297 |
2024-01-21T14:50:01 Z |
NK_ |
Nautilus (BOI19_nautilus) |
C++17 |
|
181 ms |
157780 KB |
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
const int nax = 505;
using B = bitset<nax>;
template<class T> using V = vector<T>;
using vi = V<int>;
int main() {
cin.tie(0)->sync_with_stdio(0);
int N, M, K; cin >> N >> M >> K;
V<B> A(N); for(int i = 0; i < N; i++) {
string S; cin >> S;
for(int j = 0; j < M; j++) A[i][j] = (S[j] == '.');
}
string O; cin >> O;
V<V<B>> dp(K+1, V<B>(N));
for(int i = 0; i < N; i++) dp[0][i] = A[i];
auto perform = [&](int i, char c) {
if (c == 'N') for(int r = 1; r < N; r++) dp[i + 1][r - 1] |= dp[i][r] & A[r - 1];
if (c == 'S') for(int r = 0; r < N - 1; r++) dp[i + 1][r + 1] |= dp[i][r] & A[r + 1];
if (c == 'W') for(int r = 0; r < N; r++) dp[i + 1][r] |= (dp[i][r] >> 1) & A[r];
if (c == 'E') for(int r = 0; r < N; r++) dp[i + 1][r] |= (dp[i][r] << 1) & A[r];
};
for(int i = 0; i < K; i++) {
if (O[i] == '?') for(auto& c : "NWES") perform(i, c);
else perform(i, O[i]);
// cout << "OPER: " << i << " " << O[i] << endl;
// for(int r = 0; r < N; r++) {
// for(int c = 0; c < M; c++) cout << dp[i][r][c];
// cout << nl;
// }
}
int ans = 0;
// for(int r = 0; r < N; r++) {
// for(int c = 0; c < M; c++) cout << dp.back()[r][c];
// cout << nl;
// }
for(int r = 0; r < N; r++) ans += dp.back()[r].count();
cout << ans << nl;
exit(0-0);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1116 KB |
Output is correct |
2 |
Correct |
1 ms |
1116 KB |
Output is correct |
3 |
Correct |
1 ms |
1116 KB |
Output is correct |
4 |
Correct |
1 ms |
1116 KB |
Output is correct |
5 |
Correct |
1 ms |
1116 KB |
Output is correct |
6 |
Correct |
2 ms |
1116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1116 KB |
Output is correct |
2 |
Correct |
1 ms |
1116 KB |
Output is correct |
3 |
Correct |
1 ms |
1116 KB |
Output is correct |
4 |
Correct |
1 ms |
1116 KB |
Output is correct |
5 |
Correct |
1 ms |
1116 KB |
Output is correct |
6 |
Correct |
2 ms |
1116 KB |
Output is correct |
7 |
Correct |
2 ms |
1116 KB |
Output is correct |
8 |
Correct |
1 ms |
1116 KB |
Output is correct |
9 |
Correct |
1 ms |
1116 KB |
Output is correct |
10 |
Correct |
1 ms |
976 KB |
Output is correct |
11 |
Correct |
1 ms |
860 KB |
Output is correct |
12 |
Correct |
1 ms |
1116 KB |
Output is correct |
13 |
Correct |
1 ms |
1116 KB |
Output is correct |
14 |
Correct |
1 ms |
1116 KB |
Output is correct |
15 |
Correct |
1 ms |
1116 KB |
Output is correct |
16 |
Correct |
1 ms |
1116 KB |
Output is correct |
17 |
Correct |
1 ms |
1116 KB |
Output is correct |
18 |
Correct |
1 ms |
1116 KB |
Output is correct |
19 |
Correct |
2 ms |
1272 KB |
Output is correct |
20 |
Correct |
1 ms |
1116 KB |
Output is correct |
21 |
Correct |
1 ms |
1116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1116 KB |
Output is correct |
2 |
Correct |
1 ms |
1116 KB |
Output is correct |
3 |
Correct |
1 ms |
1116 KB |
Output is correct |
4 |
Correct |
1 ms |
1116 KB |
Output is correct |
5 |
Correct |
1 ms |
1116 KB |
Output is correct |
6 |
Correct |
2 ms |
1116 KB |
Output is correct |
7 |
Correct |
2 ms |
1116 KB |
Output is correct |
8 |
Correct |
1 ms |
1116 KB |
Output is correct |
9 |
Correct |
1 ms |
1116 KB |
Output is correct |
10 |
Correct |
1 ms |
976 KB |
Output is correct |
11 |
Correct |
1 ms |
860 KB |
Output is correct |
12 |
Correct |
1 ms |
1116 KB |
Output is correct |
13 |
Correct |
1 ms |
1116 KB |
Output is correct |
14 |
Correct |
1 ms |
1116 KB |
Output is correct |
15 |
Correct |
1 ms |
1116 KB |
Output is correct |
16 |
Correct |
1 ms |
1116 KB |
Output is correct |
17 |
Correct |
1 ms |
1116 KB |
Output is correct |
18 |
Correct |
1 ms |
1116 KB |
Output is correct |
19 |
Correct |
2 ms |
1272 KB |
Output is correct |
20 |
Correct |
1 ms |
1116 KB |
Output is correct |
21 |
Correct |
1 ms |
1116 KB |
Output is correct |
22 |
Correct |
126 ms |
157520 KB |
Output is correct |
23 |
Correct |
123 ms |
157524 KB |
Output is correct |
24 |
Correct |
122 ms |
157408 KB |
Output is correct |
25 |
Correct |
120 ms |
157560 KB |
Output is correct |
26 |
Correct |
121 ms |
157528 KB |
Output is correct |
27 |
Correct |
152 ms |
157560 KB |
Output is correct |
28 |
Correct |
155 ms |
157524 KB |
Output is correct |
29 |
Correct |
156 ms |
157524 KB |
Output is correct |
30 |
Correct |
161 ms |
157524 KB |
Output is correct |
31 |
Correct |
158 ms |
157780 KB |
Output is correct |
32 |
Correct |
180 ms |
157400 KB |
Output is correct |
33 |
Correct |
180 ms |
157524 KB |
Output is correct |
34 |
Correct |
178 ms |
157556 KB |
Output is correct |
35 |
Correct |
175 ms |
157552 KB |
Output is correct |
36 |
Correct |
181 ms |
157556 KB |
Output is correct |