Submission #1269211

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269211		efeg	Nautilus (BOI19_nautilus)	C++20	100 / 100	141 ms	198228 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;
bitset<N> a[N];  
bitset<N> dp[N][5100]; 
string s; 

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

		} 
	}
	cin >> s; 

	for (int k = 0; k < m; k++){
		for (int i = 1; i <= r; i++){
			if (s[k] == 'N') dp[i][k+1] = (dp[i+1][k] & a[i]); 
			else if (s[k] == 'S') dp[i][k+1] = (dp[i-1][k] & a[i]);
			else if (s[k] == 'E') dp[i][k+1] = ((dp[i][k] << 1) & a[i]);
			else if (s[k] == 'W') dp[i][k+1] = ((dp[i][k] >> 1) & a[i]); 
			else {
				dp[i][k+1] = (dp[i+1][k] | dp[i-1][k] | (dp[i][k] << 1) | (dp[i][k] >> 1)) & a[i]; 
			}
		}
	}

	int ans = 0;
	for (int i = 1; i <= r; i++){
		ans += dp[i][m].count(); 
	}
	cout << ans << endl; 

	return 0;
}	

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