Submission #493795

#	Time	Username	Problem	Language	Result	Execution time	Memory
493795		Haruto810198	Nautilus (BOI19_nautilus)	C++17	0 / 100	3 ms	460 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;
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 == '?'){
			FOR(i, 1, r-1, 1){
				newdp[i] |= dp[i+1] & arr[i];
			}
			FOR(i, 2, r, 1){
				newdp[i] |= dp[i-1] & arr[i];
			}
			
			FOR(i, 1, r, 1){
				newdp[i] |= ((dp[i] >> 1) | (dp[i] << 1)) & arr[i];
			}
		}
		/*
		FOR(i, 1, r, 1){
			dp[i] = newdp[i];
			for(int j=c; j>=1; j--){
				if(dp[i][j] == 1) cerr<<1;
				else if(arr[i][j] == 0) cerr<<"#";
				else cerr<<" ";
			}
			cerr<<endl;
		}
		cerr<<endl;
		*/
	}

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

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

}

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