Submission #1157524

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157524		DangKhoizzzz	Nautilus (BOI19_nautilus)	C++20	100 / 100	159 ms	158816 KiB

nautilus

#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair <int , int>
#define arr3 array <int , 3>

using namespace std;

const int INF = 1e18 + 7;
const int maxn = 2e5 + 7;


int H , W , n;
bitset <502> dp[5005][505];
char s[5005] , a[505][505];

bitset <502> mark[505];

void solve()
{
    cin >> H >> W >> n;
    for(int i = 1; i <= H; i++)
    {
        for(int j = 1; j <= W; j++)
        {
            cin >> a[i][j];

            if(a[i][j] == '.')
            {
                mark[i][j] = 1;
            }
        }
    }
    for(int i = 1; i <= n; i++) cin >> s[i];

    for(int i = 1; i <= H; i++)
    {
        for(int j = 1; j <= W; j++)
        {
            if(a[i][j] == '.') dp[0][i][j] = 1;
        }
    }

    for(int k = 1; k <= n; k++)
    {
        for(int i = 1; i <= H; i++)
        {
            if(s[k] == 'E' || s[k] == '?') dp[k][i] |= (dp[k-1][i] << 1);
            if(s[k] == 'W' || s[k] == '?') dp[k][i] |= (dp[k-1][i] >> 1);
            if(s[k] == 'N' || s[k] == '?') dp[k][i] |= (dp[k-1][i+1]);
            if(s[k] == 'S' || s[k] == '?') dp[k][i] |= (dp[k-1][i-1]);

            dp[k][i] &= mark[i];
        }
    }

    int ans = 0;

    for(int i = 1; i <= H; i++)
    {
        for(int j = 1; j <= W; j++)
        {
            ans += dp[n][i][j];
        }
    }

    cout << ans << '\n';

}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

Compilation message (stderr)

nautilus.cpp:10:22: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   10 | const int INF = 1e18 + 7;
      |                 ~~~~~^~~

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