Submission #1099587

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099587		andrei_iorgulescu	Nautilus (BOI19_nautilus)	C++14	100 / 100	267 ms	154208 KiB

nautilus

#include <bits/stdc++.h>

using namespace std;

int n, m, k;
char a[505][505];
char s[5005];
bitset<250005> dp[5005];
bitset<250005> f_up, f_down, f_left, f_right;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    for (int i = 1; i <= k; i++)
        cin >> s[i];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (a[i][j] == '.')
                dp[0][(i - 1) * m + j] = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (a[i][j] == '.')
            {
                if (i - 1 >= 1 and a[i - 1][j] == '.')
                    f_up[(i - 1) * m + j] = 1;
                if (i + 1 <= n and a[i + 1][j] == '.')
                    f_down[(i - 1) * m + j] = 1;
                if (j - 1 >= 1 and a[i][j - 1] == '.')
                    f_left[(i - 1) * m + j] = 1;
                if (j + 1 <= m and a[i][j + 1] == '.')
                    f_right[(i - 1) * m + j] = 1;
            }
        }
    }
    //cout << f_left.count() << ' ' << f_right.count() << ' ' << f_up.count() << ' ' << f_down.count() << endl;
    for (int q = 1; q <= k; q++)
    {
        bitset<250005> bs_up, bs_down, bs_left, bs_right;
        bs_up = dp[q - 1] << m;
        bs_down = dp[q - 1] >> m;
        bs_left = dp[q - 1] << 1;
        bs_right = dp[q - 1] >> 1;
        //cout << bs_left.count() << ' ' << bs_right.count() << ' ' << bs_up.count() << ' ' << bs_down.count() << endl;
        for (int i = 1; i <= n; i++)
        {
            bs_left[(i - 1) * m + 1] = 0;
            bs_right[i * m] = 0;
        }
        //cout << bs_left.count() << ' ' << bs_right.count() << ' ' << bs_up.count() << ' ' << bs_down.count() << endl;
        bs_up &= f_up;
        bs_down &= f_down;
        bs_left &= f_left;
        bs_right &= f_right;
        /*if (q == k)
        {
            for (int i = 1; i <= n; i++)
            {
                for (int j = 1; j <= m; j++)
                {
                    cout << (int)bs_left[(i - 1) * m + j];
                }
                cout << endl;
            }
            cout << endl;
            for (int i = 1; i <= n; i++)
            {
                for (int j = 1; j <= m; j++)
                {
                    cout << (int)bs_right[(i - 1) * m + j];
                }
                cout << endl;
            }
            cout << endl;
            for (int i = 1; i <= n; i++)
            {
                for (int j = 1; j <= m; j++)
                {
                    cout << (int)bs_up[(i - 1) * m + j];
                }
                cout << endl;
            }
            cout << endl;
            for (int i = 1; i <= n; i++)
            {
                for (int j = 1; j <= m; j++)
                {
                    cout << (int)bs_down[(i - 1) * m + j];
                }
                cout << endl;
            }
            cout << endl;
        }*/
        //cout << bs_left.count() << ' ' << bs_right.count() << ' ' << bs_up.count() << ' ' << bs_down.count() << endl;
        if (s[q] == '?')
            dp[q] = ((bs_up | bs_down) | bs_left) | bs_right;
        else if (s[q] == 'W')
            dp[q] = bs_right;
        else if (s[q] == 'E')
            dp[q] = bs_left;
        else if (s[q] == 'S')
            dp[q] = bs_up;
        else
            dp[q] = bs_down;
        //cout << dp[q].count() << endl;
        /*for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                cout << (int)dp[q][(i - 1) * m + j];
            }
            cout << endl;
        }
        cout << endl;*/
    }
    cout << dp[k].count();
    return 0;
}

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

/**
average problema de lot juniori pe care stie sa o bage doar un om
**/

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