제출 #1282456

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1282456		TVSown	Nautilus (BOI19_nautilus)	C++20	100 / 100	209 ms	161620 KiB

nautilus

#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define szz(s) int(s.size())
#define all(s) s.begin(), s.end()
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define REP(i, a, b) for(int i = a; i >= b; --i)
const int N = 5000 + 5;
int n, m, k;
int a[N][N];
string tt, s;


namespace sub2{
    int dp[105][105][105];
    void solve(){
        FOR(i, 1, n){
            FOR(j, 1, m) if(a[i][j]) dp[0][i][j] = 1;
        }

        FOR(t, 0, k - 1){
            FOR(i, 1, n){
                FOR(j, 1, m){
                    if(dp[t][i][j]){
                        if(s[t] == 'N' || s[t] == '?'){
                            if(a[i - 1][j]) dp[t + 1][i - 1][j] = 1;
                        }
                        if(s[t] == 'S' || s[t] == '?'){
                            if(a[i + 1][j]) dp[t + 1][i + 1][j] = 1;
                        }
                        if(s[t] == 'W' || s[t] == '?'){
                            if(a[i][j - 1]) dp[t + 1][i][j - 1] = 1;
                        }
                        if(s[t] == 'E' || s[t] == '?'){
                            if(a[i][j + 1]) dp[t + 1][i][j + 1] = 1;
                        }
                    }
                }
            }

//            FOR(i, 1, n){
//                FOR(j, 1, m) cout << dp[t][i][j] << " ";
//                cout << "\n";
//            }
//            cout << "\n";
        }

        int res = 0;
        FOR(i, 1, n){
            FOR(j, 1, m){
                if(dp[k][i][j]) ++res;
            }
        }
        cout << res;
    }
}

namespace ac{
    bitset<505> dp[5005][505];
    void solve(){
        FOR(i, 1, n){
            FOR(j, 1, m) if(a[i][j]) dp[0][i].set(j);
        }
        s = "#" + s;
        FOR(t, 1, k){
            if(s[t] == 'N' || s[t] == '?'){
                FOR(i, 1, n){
                    dp[t][i] |= dp[t - 1][i + 1];
                    dp[t][i] &= dp[0][i];
                }
            }
            if(s[t] == 'S' || s[t] == '?'){
                FOR(i, 1, n){
                    dp[t][i] |= dp[t - 1][i - 1];
                    dp[t][i] &= dp[0][i];
                }
            }
            if(s[t] == 'W' || s[t] == '?'){
                FOR(i, 1, n){
                    dp[t][i] |= (dp[t - 1][i] >> 1);
                    dp[t][i] &= dp[0][i];
                }
            }
            if(s[t] == 'E' || s[t] == '?'){
                FOR(i, 1, n){
                    dp[t][i] |= (dp[t - 1][i] << 1);
                    dp[t][i] &= dp[0][i];
                }
            }

//            FOR(i, 1, n){
//                FOR(j, 1, m) cout << dp[t][i][j] << " ";
//                cout << "\n";
//            }
//            cout << "\n";
        }

        int res = 0;
        FOR(i, 1, n){
            FOR(j, 1, m){
                if(dp[k][i][j]) ++res;
            }
        }
        cout << res;
    }
}

void solve(){
    cin >> n >> m >> k;
    FOR(i, 1, n){
        cin >> tt;
        FOR(j, 1, m){
            a[i][j] = tt[j - 1] == '.';
//            cout << a[i][j] << " ";
        }
//        cout << "\n";
    }
    cin >> s;

//    sub2::solve();
    ac::solve();
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    solve();
}

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