Submission #1087136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087136		ZeroCool	Nautilus (BOI19_nautilus)	C++14	100 / 100	171 ms	1116 KiB

nautilus

#include <bits/stdc++.h>

using namespace std;

#define ar array
#define int long long
#define ld long double
#define crash assert(69 == 420)

const int MOD = 1e9 + 7;
const int INF = 1e17;
const int N = 525;
const int LOG = 20;

bitset<N> dp[2][N];
bitset<N> A[N];

signed main(){ios_base::sync_with_stdio(false);cin.tie(0);
	int n, m, k;
	cin>>n>>m>>k;
	string s[n];
	for(int i = 0;i < n;i++)cin>>s[i];
	for(int i = 0;i < n;i++){
		for(int j = 0;j < m;j++){
			A[i][j] = (s[i][j] == '.');
		}

	}
	string t;
	cin>>t;
	for(int i = 0;i < n;i++){
		for(int j = 0;j < m;j++)dp[0][i][j] = A[i][j];
	}
	int p = 0;
	for(int i = 0;i < k;i++){
		for(int j = 0; j < n;j++)dp[p ^ 1][j].reset();

		for(int j = 0;j < n;j++){
			if(t[i] == 'W' || t[i] == '?')dp[p ^ 1][j] |= (A[j] & (dp[p][j] >> 1));
			if(t[i] == 'E' || t[i] == '?')dp[p ^ 1][j] |= (A[j] & (dp[p][j] << 1));
			if((t[i] == 'N' || t[i] == '?') && j + 1 < n)dp[p ^ 1][j] |= (dp[p][j + 1] & A[j]);
			if((t[i] == 'S' || t[i] == '?') && j - 1 >= 0)dp[p ^ 1][j] |= (dp[p][j - 1] & A[j]);

		}
		p ^= 1;
	}
	int ans = 0 ;
	for(int i = 0;i < n;i++){
		ans += dp[p][i].count();
		//for(int j = 0;j < m;j++)cout<<dp[p][i][j]<<" ";
		//cout<<'\n';
	}
	cout<<ans;
}

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