Submission #914297

#	Time	Username	Problem	Language	Result	Execution time	Memory
914297		NK_	Nautilus (BOI19_nautilus)	C++17	100 / 100	181 ms	157780 KiB

nautilus

// 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);
}

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