Submission #914297

# Submission time Handle Problem Language Result Execution time Memory
914297 2024-01-21T14:50:01 Z NK_ Nautilus (BOI19_nautilus) C++17
100 / 100
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