Submission #1269169

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269169		efeg	Nautilus (BOI19_nautilus)	C++20	29 / 100	6 ms	708 KiB

nautilus

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")

#define int long long 
#define F first
#define S second 
#define pb push_back
#define endl '\n'
#define all(v) v.begin(),v.end()
#define gcd(a,b) __gcd(a,b)
#define mt make_tuple
#define pqueue priority_queue


typedef pair<int,int> ii;
typedef tuple<int,int,int> iii;
typedef tuple<int,int,int,int> iiii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<iii> viii;
typedef set<int> si;
typedef vector<ii> vii;				
typedef vector<vi> vvi;
typedef vector<si> vsi;
typedef vector<vb> vvb;
typedef vector<vc> vvc;

const int MOD = 1e9 + 7;
const int N = 600;  

int r,c,m; 
char a[N][N]; 
string s; 
bitset<N> old[N]; 

string tmp = "NESW"; 
int dX[] = {-1,0,1,0};
int dY[] = {0,1,0,-1};


int32_t main(){
	ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	cin >> r >> c >> m; 
	for (int i = 0; i < r; i++){
		for (int j = 0; j < c; j++){
			cin >> a[i][j]; 
			old[i][j] = (a[i][j] == '.'); 
		} 
	}
	cin >> s; 

	auto check = [&](int i,int j) -> bool{
		return (i > -1 && i < r && j > -1 && j < c && old[i][j]);
	}; 

	for (int x = m-1; x > -1; x--){
		int dir = -1;
		for (int i = 0; i < 4; i++){
			if (tmp[i] == s[x]) dir = i; 
		}
		bitset<N> nw[N];
		for (int i = 0; i < r; i++){
			for (int j = 0; j < c; j++){
				if (a[i][j] == '.'){
					if (dir != -1){
						if (check(i + dX[dir],j + dY[dir])){
							nw[i][j] = 1; 
						}
					}	
					else {
						for (int dir = 0; dir < 4; dir++){
							if (check(i + dX[dir],j + dY[dir])){
								nw[i][j] = 1;
								break; 
							}
						}
					}
				}
			//	cout << nw[i][j] << " ";
			}
			//cout << endl; 
		}
//		cout << endl; 
		for (int i = 0; i < r; i++){
			old[i] = nw[i]; 
		}
	}
	int ans = 0;
	for (int i = 0; i < r; i++) ans += old[i].count(); 
	cout << ans << endl; 


	return 0;
}	

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