Submission #1136674

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136674		mmdrzada	Nautilus (BOI19_nautilus)	C++20	100 / 100	81 ms	1020 KiB

nautilus

// Nautilus

// Village
// Alphine walley


#include <bits/stdc++.h>

using namespace std;

#define vi vector<int>
#define REP(i, k) for(int i = 0 ; i < k ; i ++)
#define pb push_back
#define pii pair<int, int>
#define ll long long
#define sep ' '
#define F first
#define S second

const int N = 501, M = 5001;
int r, c, m;
string s[N];
string t;
bitset<N> dp[2][N];
bitset<N> emp[N];

pii change(pii curr, char c) {
    if (c == 'N') curr.F++;
    else if (c == 'S') curr.F--;
    if (c == 'E') curr.S--;
    if (c == 'W') curr.S++;
    return curr;
}

bool valid(int i, int j) {
    return 0 <= i && i < r && 0 <= j && j < c;
}

bool check(int i, int j) {
    if (s[i][j] == '#') return false;
    pii curr = {i, j};
    for(char c: t) {
        pii ne = change(curr, c);
        if (valid(ne.F, ne.S) && s[ne.F][ne.S] != '#') curr = ne;
        else return false;
    }
    return true;
}

void solve() {
    cin >> r >> c >> m;
    REP(i, r) cin >> s[i];
    cin >> t;
    
    REP(i, r) {
    	REP(j, c) {
    		emp[i][j] = dp[1][i][j] = s[i][j] != '#';
    	}
    }
    
    for(int i = 0 ; i < m ; i ++) {
    	int curr= i%2;
    	if (t[i] == 'N') {
    		for(int j = 0 ; j < r ; j ++) {
    			if (j == r-1) dp[curr][j].reset();
    			else dp[curr][j] = dp[1-curr][j+1];
    		}
    	} else if (t[i] == 'E') {
    		for(int j = 0 ; j < r ; j ++) {
    			dp[curr][j] = dp[1-curr][j]<<1;
    		}
    	} else if (t[i] == 'S') {
    		for(int j = 0 ; j < r ; j ++) {
    			if (j == 0) dp[curr][j].reset();
    			else dp[curr][j] = dp[1-curr][j-1];
    		}
    	} else if (t[i] == 'W') {
    		for(int j = 0 ; j < r ; j ++) {
    			dp[curr][j] = dp[1-curr][j]>>1;
    		}
    	} else {
    		for(int j = 0 ; j < r ; j ++) {
    			dp[curr][j] = (dp[1-curr][j]>>1) | (dp[1-curr][j]<<1);
    			if (j > 0) dp[curr][j] |= dp[1-curr][j-1];
    			if (j < r) dp[curr][j] |= dp[1-curr][j+1];
    		}
    	}
    	for(int j = 0 ; j < r ; j ++) dp[curr][j] &= emp[j];
    }
    int ans = 0;
    REP(i, r) {
    	REP(j, c) {
    		ans += dp[1-m%2][i][j];
    	}
    }
    cout << ans << endl;
}

int32_t main() {
    
    solve();

    return 0;
}

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