Submission #1244788

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244788		altern23	Nautilus (BOI19_nautilus)	C++20	100 / 100	192 ms	160636 KiB

nautilus

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const int MAXN = 5e5;
const ll INF = 1e18;
const int MOD = 1e9 + 7;
const ld eps = 1e-6;	

char grid[505][505];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);		
	int tc = 1;	
	// cin >> tc;
	for(;tc--;){
		ll R, C, M; cin >> R >> C >> M;
		vector<vector<bitset<505>>> dp(R + 5, vector<bitset<505>>(M + 5));
		vector<bitset<505>> water(R + 5);
		
		for(int i = 1; i <= R; i++){
			for(int j = 1; j <= C; j++){
				cin >> grid[i][j];
				if(grid[i][j] == '.'){
					water[i][j] = dp[i][0][j] = 1;
				}
			}
		}
		
		string s; cin >> s;
		s = '%' + s;
		for(int round = 1; round <= M; round++){
			for(int i = 1; i <= R; i++){
				if(s[round] == 'N'){
					dp[i][round] = dp[i + 1][round - 1];
				}
				else if(s[round] == 'S'){
					dp[i][round] = dp[i - 1][round - 1];
				}
				else if(s[round] == 'W'){
					dp[i][round] = (dp[i][round - 1] >> 1);
				}
				else if(s[round] == 'E'){
					dp[i][round] = (dp[i][round - 1] << 1);
				}
				else{
					dp[i][round] |= dp[i + 1][round - 1];
					dp[i][round] |= dp[i - 1][round - 1];
					dp[i][round] |= (dp[i][round - 1] >> 1);
					dp[i][round] |= (dp[i][round - 1] << 1);
				}
				dp[i][round] &= water[i];
			}
		}
		
		ll ans = 0;
		for(int i = 1; i <= R; i++){
			for(int j = 1; j <= C; j++) ans += dp[i][M][j];
		}
		
		cout << ans << "\n";
	}
}

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