Submission #891588

#	Time	Username	Problem	Language	Result	Execution time	Memory
891588		vjudge1	Nautilus (BOI19_nautilus)	C++17	100 / 100	154 ms	1364 KiB

nautilus

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <fstream>
#include <unordered_map>
using namespace std;

typedef long long ll;
typedef long double ld;

#define all(x) x.begin(),x.end()
#define pb push_back
#define ent "\n"

#define int long long

const int maxn = (int)1e6 + 13;
const ll inf = (long long)1e18 + 20;
const int mod = (int)1e9 + 7;

int n,m,k;
char a[501][501];

void solve(){
	cin >> n >> m >>k;
	bitset<500>ok[n],ans[n],s[n],d[n],f[n],g[n],r[n], cl;
	for(int i = 0 ; i < n ; i ++){
		for(int j = 0 ; j < m ; j ++){
			cin >> a[i][j];
			if(a[i][j] == '.'){
				ok[i][j] = 1;
				ans[i][j] = 1;
			}
			else{
				ok[i][j] = 0;
				ans[i][j] = 0;
			}
		}
	}
	string S;cin >> S;
	for(int i = 0 ; i < k ; i ++){
		if(S[i] == 'E'){
			for(int j = 0 ; j < n ; j ++){
				ans[j] <<= 1;
				ans[j] &= ok[j];
			}
		}
		if(S[i ] == 'W'){
			for(int j = 0 ; j < n ; j ++){
				ans[j] >>= 1;
				ans[j] &= ok[j];
			}
		}
		if(S[i] == 'N'){
			for(int j = 0 ; j < n - 1 ; j ++){
				ans[j] = ans[j + 1] & ok[j];
			}
			for(int j = 0 ; j < m ; j ++){
				ans[n - 1][j] = 0;
			}
		}
		if(S[i] == 'S'){
			for(int j = n - 1 ; j > 0 ; j --){
				ans[j] = ans[j - 1] & ok[j];
			}
			for(int j = 0 ; j < m ; j ++){
				ans[0][j] = 0;
			}
		}
		if(S[i] == '?'){
			for(int j = 0 ; j < n ; j ++){
				s[j] = ans[j];
				d[j] = ans[j];
				f[j] = ans[j];
				g[j] = ans[j];
			}
			for(int j = 0 ; j < n ; j ++){
				s[j] >>= 1;
			}
			for(int j = 0 ; j < n ; j ++){
				d[j] <<= 1;
			}
			for(int j = 0 ; j < n - 1 ; j ++){
				f[j] = ans[j + 1];
			}
			for(int j = n - 1 ; j > 0 ; j --){
				g[j] = ans[j - 1];
			}
			for (int i = 0; i < m; ++ i) f[n - 1][i] = 0,g[0][i] = 0;
			for(int j = 0 ; j < n ; j ++){
				r[j] = (s[j] | d[j] | f[j] | g[j]);
				r[j] &= ok[j];
				ans[j] = r[j];
			}
		}
	}
	int res = 0;
	for(int i = 0 ; i < n ; i ++){
		for(int j = 0 ; j < m ; j ++){
			res += ans[i][j];
		}
	}
	cout << res;
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t --){
		solve();
	}
	return 0;
}

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