Submission #1269206

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269206		efeg	Nautilus (BOI19_nautilus)	C++20	66 / 100	1093 ms	580 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){
		return (i > -1 && i < r && j > -1 && j < c); 
	};

	for (int k = 0; k < m; k++){
		int dir = -1;
		for (int x = 0; x < 4; x++){
			if (tmp[x] == s[k]) dir = x; 
		}

		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){
						int oldi = i - dX[dir], oldj = j - dY[dir];
						if (check(oldi,oldj) && old[oldi][oldj]){
							nw[i][j] = 1; 
						}
					}
					else {
						for (int x = 0; x < 4; x++){
							int oldi = i - dX[x], oldj = j - dY[x]; 
							if (check(oldi,oldj) && old[oldi][oldj]){
								nw[i][j] = 1; 
							}
						}
					}
				}
					
			}
		}
		
		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: 37 / 37
• Subtask 3: 0 / 34