Submission #1108744

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108744		MrPavlito	Nautilus (BOI19_nautilus)	C++17	100 / 100	162 ms	828 KiB

nautilus

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define sc second
#define endl "\n"
#define pii pair<int,int>

using namespace std;

const int MAXN =505;
const int mod7 = 1e9+7;
const long long inf = 1e18;

vector<bitset<MAXN>> matrica(MAXN);
vector<pair<bitset<MAXN>, bitset<MAXN>>> dp(MAXN);


signed main()
{
    ios_base::sync_with_stdio(false),cin.tie(0), cout.tie(0);
    int tt=1;
    //cin >> tt;
    while(tt--)
    {
        int n,m, k;
        cin >> n >> m >> k;
        string str;
        for(int i=1; i<=n; i++)
        {
            string s;cin >> s;
            for(int j=1;j<=m; j++)
            {
                if(s[j-1] == '.')
                {
                    matrica[i][m-j+1] = 1;
                    dp[i].fi[m-j+1] = 1;
                }
            }
        }
        cin >> str;
        for(int p = 0;p<k; p++)
        {
            if(str[p] == '?')
            {
                for(int i=1; i<=n; i++)
                {
                    dp[i].sc=(dp[i-1].fi|dp[i+1].fi|(dp[i].fi << 1)|(dp[i].fi >> 1));
                }
            }
            else
            {
                if(str[p] == 'N') for(int i=1; i<=n; i++)dp[i].sc=dp[i+1].fi;
                else if(str[p] == 'S') for(int i=1; i<=n; i++)dp[i].sc=dp[i-1].fi;
                else if(str[p] == 'W')  for(int i=1; i<=n; i++)dp[i].sc = (dp[i].fi << 1);
                else for(int i=1; i<=n; i++)dp[i].sc = (dp[i].fi >> 1);
            }
            for(int i=1; i<=n; i++)dp[i].sc&= matrica[i];
            for(int i=1; i<=n; i++)dp[i].fi = dp[i].sc;
        }
        int rez = 0;
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                rez+= dp[i].fi[j];
            }
        }
        cout << rez << endl;



    }
}

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