Submission #414988

#	Time	Username	Problem	Language	Result	Execution time	Memory
414988		Hideo	Nautilus (BOI19_nautilus)	C++17	100 / 100	144 ms	984 KiB

nautilus

#include <bits/stdc++.h>
using namespace std;

#define all(s) s.begin(), s.end()
#define ll long long
#define fr first
#define sc second
#define pb push_back
#define mk make_pair

const int N = 507;
const int INF = 1e9 + 7;

string a[N];
string s;
int n, m, k;
bitset < 507 > dp[N][2], b[N];

main (){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        a[i] = ' ' + a[i];
        for (int j = 1; j <= m; j++){
            if (a[i][j] == '.'){
                dp[i][0][j - 1] = 1;
                b[i][j - 1] = 1;
            }
        }
    }
    cin >> s;
    int cur = 0;
    for (int c = 0; c < k; c++){
        cur ^= 1;
        for (int i = 1; i <= n; i++){
            if (s[c] == 'N'){
                dp[i][cur] = dp[i + 1][cur ^ 1];
            }
            if (s[c] == 'W'){
                dp[i][cur] = dp[i][cur ^ 1] >> 1;
                dp[i][cur][m - 1] = 0;
            }
            if (s[c] == 'E'){
                dp[i][cur] = dp[i][cur ^ 1] << 1;
            }
            if (s[c] == 'S'){
                dp[i][cur] = dp[i - 1][cur ^ 1];
            }
            if (s[c] == '?'){
                dp[i][cur] = (dp[i][cur ^ 1] >> 1) ;
                dp[i][cur][m - 1] = 0;
                dp[i][cur] |= dp[i - 1][cur ^ 1];
                dp[i][cur] |= dp[i][cur ^ 1] << 1;
                dp[i][cur] |= dp[i + 1][cur ^ 1];
            }
            dp[i][cur] &= b[i];
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
//            cout << dp[i][cur][j - 1];
            if (dp[i][cur][j - 1])
                ans++;
        }
//        cout << endl;
    }
    cout << ans;
}

//5 9 7
//...##....
//..#.##..#
//..#....##
//.##...#..
//....#....
//WS?EE??

Compilation message (stderr)

nautilus.cpp:19:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   19 | main (){
      | ^~~~

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