Submission #242963

#	Time	Username	Problem	Language	Result	Execution time	Memory
242963		socho	Nautilus (BOI19_nautilus)	C++14	100 / 100	234 ms	32540 KiB

nautilus

#include "bits/stdc++.h"
using namespace std;
void fast() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
}
void ran() {
	srand(chrono::steady_clock::now().time_since_epoch().count());
}
long long get_rand() {
	long long a = rand();
	long long b = rand();
	return a * (RAND_MAX + 1ll) + b; 
}
// #define endl '\n'
// #define double long double
// #define int long long
// int MOD = 1000 * 1000 * 1000;
// int MOD = 998244353;

const int MXN = 505, MXT = 1005;
bitset<MXN> sea[MXN], inr[MXN];
int n, m, k;

bitset<MXN> dp[MXN][MXT];

signed main() {
	
	ran(); fast();
	
	for (int i=0; i<MXN; i++) {
		for (int j=0; j<MXN; j++) {
			sea[i][j] = 0;
			inr[i][j] = 0;
			dp[i][j] = 0;
		}
	}
	
	cin >> n >> m >> k;
	for (int i=0; i<n; i++) {
		string s;
		cin >> s;
		for (int j=0; j<m; j++) {
			if (s[j] == '.') sea[i][j] = dp[i][0][j] = true;
			inr[i][j] = true;
		}
	}
	
	string s;
	cin >> s;
	int f = 0;
	
	for (auto x: s) {
		if (x == 'E') {
			for (int i=0; i<n; i++) {
				dp[i][f+1] = (dp[i][f] << 1) & sea[i];
			}
		}
		else if (x == 'W') {
			for (int i=0; i<n; i++) {
				dp[i][f+1] = (dp[i][f] >> 1) & sea[i];
			}
		}
		else if (x == 'N') {
			for (int i=0; i<n; i++) {
				if (i == n-1) {
					// empty line
					dp[i][f+1] = sea[MXN-1];
				}
				else {
					// normal
					dp[i][f+1] = dp[i+1][f] & sea[i];
				}
			}
		}
		else if (x == 'S') {
			for (int i=0; i<n; i++) {
				if (i == 0) {
					// empty line
					dp[i][f+1] = sea[MXN-1];
				}
				else {
					// normal
					dp[i][f+1] = dp[i-1][f] & sea[i];
				}
			}
		}
		else {
			// any
			for (int i=0; i<n; i++) {
				if (i == 0) {
					dp[i][f+1] = (dp[i+1][f] | (dp[i][f] << 1) | (dp[i][f] >> 1)) & sea[i];
				}
				else if (i == n-1) {
					dp[i][f+1] = (dp[i-1][f] | (dp[i][f] << 1) | (dp[i][f] >> 1)) & sea[i];
				}
				else {
					dp[i][f+1] = (dp[i+1][f] | dp[i-1][f] | (dp[i][f] << 1) | (dp[i][f] >> 1)) & sea[i];
				}
			}
		}
		f++;
	}
	
	int x = 0;
	for (int i=0; i<n; i++) {
		for (int j=0; j<m; j++) {
			if (dp[i][f][j]) x++;
		}
	}
	cout << x << endl;
	
}

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