Submission #643745

#	Time	Username	Problem	Language	Result	Execution time	Memory
643745		amoorj	Nautilus (BOI19_nautilus)	C++17	100 / 100	142 ms	159108 KiB

nautilus

#pragma GCC optimize ("O3,unroll-loops,Ofast")
#pragma GCC target ("avx2,bmi,bmi2,popcnt")
#include <bits/stdc++.h>
#define F first
#define pb push_back
#define sz size()
#define S second
using namespace std;
typedef long long int ll;

const int N = 505, M = 5005;
int r,c,m;
string wef,s[N];
bitset<N> dp[M][N], row[N]; // dp[m][r][c] 

inline void init(){
}
inline void input(){
	cin >> r >> c >> m;
	for(int i=0;i<r;i++)
		cin >> s[i];
	cin >> wef;
}
inline void solve(){
	for(int i=0;i<r;i++){
		for(int j=0;j<c;j++){
			if(s[i][j] == '.'){
				dp[0][i][j] = 1;
				row[i][j] = 1;
			}
		}
	}
	for(int i=1;i<=m;i++){
		for(int y=0;y<r;y++){
				if((wef[i-1] == 'N' || wef[i-1] == '?') && y < r-1)
					dp[i][y] = (dp[i][y] | (row[y] & row[y+1] & dp[i-1][y+1]));
				if((wef[i-1] == 'S' || wef[i-1] == '?') && y > 0)
					dp[i][y] = (dp[i][y] | (row[y] & row[y-1] & dp[i-1][y-1]));
				if(wef[i-1] == 'W' || wef[i-1] == '?')
					dp[i][y] = (dp[i][y] | (row[y] & (row[y] >> 1) & (dp[i-1][y] >> 1)));
				if(wef[i-1] == 'E' || wef[i-1] == '?')
					dp[i][y] = (dp[i][y] | (row[y] & (row[y] << 1) & (dp[i-1][y] << 1)));
		}
	}
/*	for(int i=0;i<r;i++){
		for(int j=0;j<c;j++)
			cout << row[i][j];
		cout << endl;
	}	
	cout << endl;
	int cnt = 0;
	for(int i=0;i<r;i++){
		for(int j=0;j<c;j++)
			cout << dp[1][i][j];
		cout << endl;
	}*/
	int cnt = 0;
	for(int i=0;i<r;i++)
		for(int j=0;j<c;j++)
			cnt += dp[m][i][j];
	cout << cnt;
}
int main(){
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
	init();
	int queries = 1;
//	cin >> queries;
	while(queries--){
		input();
		solve();
	}
	return 0;
}

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