Submission #493801

#	Time	Username	Problem	Language	Result	Execution time	Memory
493801		Haruto810198	Nautilus (BOI19_nautilus)	C++17	66 / 100	1096 ms	9668 KiB

nautilus

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = INT_MAX;
const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

const int MAX = 5010;

int r, c, m;
string str;
vector<bitset<MAX>> arr(MAX), dp(MAX), newdp(MAX);
int res;

signed main(){
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin>>r>>c>>m;
	FOR(i, 1, r, 1){
		FOR(j, 1, c, 1){
			char ch;
			cin>>ch;
			if(ch == '.') dp[i][c+1-j] = arr[i][c+1-j] = 1;
		}
	}

	cin>>str;
	for(char ch : str){
		
		FOR(i, 1, r, 1){
			newdp[i].reset();
		}
		
		if(ch == 'N'){
			FOR(i, 1, r-1, 1){
				newdp[i] |= dp[i+1] & arr[i];
			}
		}
		if(ch == 'S'){
			FOR(i, 2, r, 1){
				newdp[i] |= dp[i-1] & arr[i];
			}
		}
		if(ch == 'E'){
			FOR(i, 1, r, 1){
				newdp[i] |= (dp[i] >> 1) & arr[i];
			}
		}
		if(ch == 'W'){
			FOR(i, 1, r, 1){
				newdp[i] |= (dp[i] << 1) & arr[i];
			}
		}
		
		if(ch == '?'){
			newdp[1] |= dp[2] & arr[1];
			FOR(i, 2, r-1, 1){
				newdp[i] |= (dp[i-1] | dp[i+1]) & arr[i];
			}
			newdp[r] |= dp[r-1] & arr[r];
			
			FOR(i, 1, r, 1){
				newdp[i] |= ((dp[i] >> 1) | (dp[i] << 1)) & arr[i];
			}
		}
		
		swap(dp, newdp);
				
	}

	FOR(i, 1, r, 1){
		FOR(j, 1, c, 1){
			res += dp[i][j];
		}
	}

	cout<<res<<'\n';
	
	return 0;

}

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