제출 #931063

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
931063		efedmrlr	Nautilus (BOI19_nautilus)	C++17	100 / 100	208 ms	1112 KiB

nautilus

#include <bits/stdc++.h>

using namespace std;


#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()


void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}


const double EPS = 0.00001;
const int INF = 1e9+500;
const int N = 505;
const int M = 5005;
const int ALPH = 26;
const int LGN = 25;
constexpr int MOD = 1e9+7;
int r,c,m;
vector<array<int,2> > direct = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // 0 - down, 1 - up, 2 - right, 3 - left
vector<bitset<N> > gr(N, bitset<N>());
vector<int> seq(1,10);
vector<bitset<N> > dp, dpn;
bitset<N> empt;
inline void solve() {
    cin >> r >> c >> m;
    for(int i = 1; i<= r; i++) {
        for(int j = 1; j <= c; j++) {
            char tmp;
            cin >> tmp;
            if(tmp == '.') {
                gr[i][j] = 1;
            }
            
        }
    }
    for(int i = 1; i<=m; i++) {
        char tmp;
        cin >> tmp;
        if(tmp == 'S') {
            seq.pb(1);
        }
        else if(tmp == 'N') {
            seq.pb(0);
        }
        else if(tmp == 'E') {
            seq.pb(3);
        }
        else if(tmp == 'W') {
            seq.pb(2);
        }
        else {
            seq.pb(4);
        }
    
        
    }
    dp.assign(r + 3, bitset<N>());
    dpn.assign(r + 3, bitset<N>());
    
    for(int i = 1; i <= r; i++) {
        dp[i] = gr[i];
    }
    for(int k = 1; k <= m; k++) {
        for(int i = 1; i<=r; i++) {
            dp[i] &= gr[i];
            dpn[i] = empt;
        }
        if(seq[k] == 0 || seq[k] == 4) {
            for(int i = 1; i <= r; i++) {
                dpn[i] = dpn[i] | dp[i + 1];
            }
        }
        if(seq[k] == 1 || seq[k] == 4) {
            for(int i = 1; i <= r; i++) {
                dpn[i] = dpn[i] | dp[i - 1];
            }
        }
        if(seq[k] == 2 || seq[k] == 4) {
            for(int i = 1; i<=r; i++) {
                dpn[i] = dpn[i] | (dp[i] >> 1);
            }
        }
        if(seq[k] == 3 || seq[k] == 4) {
            for(int i = 1; i<=r; i++) {
                dpn[i] = dpn[i] | (dp[i] << 1);
            }
        } 
        
        swap(dp, dpn);
    }
    int ans = 0;
    for(int i = 1; i<=r; i++) {
        dp[i] &= gr[i];
    }
    for(int i = 1; i<=r; i++) {
        for(int j = 1; j <= c; j++) {
                ans += dp[i][j]; 
        }
    }
    cout << ans << "\n";
}
 
signed main() {

    fastio();
    int test = 1;
    //cin>>test;
    while(test--) {
        solve();
    }
    
}

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