Submission #493808

#TimeUsernameProblemLanguageResultExecution timeMemory
493808Haruto810198Nautilus (BOI19_nautilus)C++17
66 / 100
1092 ms9776 KiB
#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){
			
		if(ch == 'N'){
			FOR(i, 1, r-1, 1){
				newdp[i] = dp[i+1] & arr[i];
			}
			newdp[r].reset();
		}
		if(ch == 'S'){
			newdp[1].reset();
			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];
			FOR(i, 2, r-1, 1){
				newdp[i] = dp[i-1] | dp[i+1];
			}
			newdp[r] = dp[r-1];
			
			FOR(i, 1, r, 1){
				newdp[i] |= (dp[i] >> 1) | (dp[i] << 1);
			}

			FOR(i, 1, r, 1){
				newdp[i] &= arr[i];
			}
		}
		
		swap(dp, newdp);
		
	}

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

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

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...