Submission #237570

#	Time	Username	Problem	Language	Result	Execution time	Memory
237570		grt	Nautilus (BOI19_nautilus)	C++17	100 / 100	207 ms	888 KiB

nautilus

#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
#define _ ios_base::sync_with_stdio(0); cin.tie(0);
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

using namespace std;

using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int nax = 502;
int r,c,m;
string s;

bitset<nax>dp[nax], mp[nax], tmp[nax];

int main() {_
	cin >> r >> c >> m;
	for(int i = 1; i <= r; ++i) {
		for(int j = 1; j <= c; ++j) {
			char t;
			cin >> t;
			if(t == '.') {
				dp[i].set(j);
				mp[i].set(j);
			}
		}
	}
	cin >> s;
	for(int i = 0; i < m; ++i) {
		if(s[i] == 'N') {
			for(int j = 1; j <= r; ++j) {
				dp[j] = (dp[j+1] & mp[j]);
			}
		} else if(s[i] == 'S') {
			for(int j = r; j >= 1; --j) {
				dp[j] = (dp[j-1] & mp[j]);
			}
		} else if(s[i] == 'W') {
			for(int j = 1; j <= r; ++j) {
				dp[j] = ((dp[j] >> 1) & mp[j]);
			}
			
		} else if(s[i] == 'E') {
			for(int j = 1; j <= r; ++j) {
				dp[j] = ((dp[j] << 1) & mp[j]);
			}
		} else {
			for(int j = 1; j <= r; ++j) {
				tmp[j] = (((dp[j] << 1) | (dp[j] >> 1) | (dp[j+1]) | (dp[j-1])) & mp[j]);
			}
			for(int j = 1; j <= r; ++j) {
				dp[j] = tmp[j];
			}
		}
	}
	int ans = 0;
	for(int i = 1; i <= r; ++i) {
		ans += dp[i].count();
	}
	cout << ans;
	
}

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