Submission #925720

#	Time	Username	Problem	Language	Result	Execution time	Memory
925720		vjudge1	Nautilus (BOI19_nautilus)	C++17	100 / 100	156 ms	1500 KiB

nautilus

#include<iostream>
#include<cassert>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
#include<set>
#include<queue>
#include<map>
#include<iomanip>
#include<bitset>

using namespace std;

const int N = (int)4e5 + 7;
const int inf = (int)1e9 + 7;
const int MOD = (int)998244353;
const long long INF = (long long)1e18 + 7; 

int mult(int x, int y) {
	return 1ll*x*y%MOD;
}

int sum(int x, int y) {
	x += y;
	if(x >= MOD) {
		x -= MOD;
	}
	return x;
}

int sub(int x, int y) {
	x -= y;
	if(x < 0) {
		x += MOD;
	}
	return x;
}

int n, m, k;

vector<pair<int, int> > dir[300];

void init() {
	dir['W'] = {{0, -1}};
	dir['E'] = {{0, +1}};
	dir['N'] = {{-1, 0}};
	dir['S'] = {{+1, 0}};
	dir['?'] = {{0, -1}, {0, +1}, {-1, 0}, {+1, 0}};
}

int main() {	
	ios_base::sync_with_stdio(NULL);
	cin.tie(0);
	init();
	cin >> n >> m >> k;
	char a[n+1][m+1];
	bool is[n+1][m+1];
	bitset<505> used[2][501];
	bitset<505> block[501];
	memset(is, 0, sizeof(is));
	for(int i = 0; i < n; ++i) {
		used[1][i].reset();
		for(int j = 0; j < m; ++j) {
			cin >> a[i][j];
			if(a[i][j] == '.') {
				used[0][i][j]=1;
			} else {
				block[i][j]=1;
			}
		}
	}
	string s;
	cin >> s;
	s = '#'+s;
	for(int id = 1; id <= k; ++id) {
		if(s[id] == 'W' || s[id] == '?') {
			for(int i = 0; i < n; ++i) {
				used[1][i] |= (used[0][i]>>1);
			}			
		}
		if(s[id] == 'E' || s[id] == '?') {
			for(int i = 0; i < n; ++i) {
				used[1][i] |= (used[0][i]<<1);
			}
		}
		if(s[id] == 'N' || s[id] == '?') {
			for(int i = 0; i < n-1; ++i) {
				used[1][i] |= used[0][i+1];		
			}
		}
		if(s[id] == 'S' || s[id] == '?') {
			for(int i = 1; i < n; ++i) {
				used[1][i] |= used[0][i-1];
			}
		}
		for(int i = 0; i < n; ++i) {
			used[1][i] |= block[i];
			used[1][i] ^= block[i];
	    	used[0][i] = used[1][i];    
	    	used[0][i][m] = 0;
	    	used[1][i].reset();
		}
	}
	int ans = 0;
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < m; ++j) {
			if(used[0][i][j]) {
				assert(a[i][j] == '.');
			}
			ans += used[0][i][j];
		}
	}
	cout << ans << "\n";
	return 0;
}

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