Submission #888817

#	Time	Username	Problem	Language	Result	Execution time	Memory
888817		12345678	Nautilus (BOI19_nautilus)	C++17	66 / 100	1078 ms	1116 KiB

nautilus

#include <bits/stdc++.h>

using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

const int nx=505;
int r, c, m, dx[4]={1, 0, 0, -1}, dy[4]={0, 1, -1, 0}, en[100], cnt;
char mp[nx][nx];
bool dp[2][nx][nx];
string s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    en['N']=1; en['W']=0; en['E']=3; en['S']=2;
    cin>>r>>c>>m;
    for (int i=1; i<=r; i++) for (int j=1; j<=c; j++) cin>>mp[i][j], dp[0][i][j]=(mp[i][j]=='.');
    cin>>s;
    for (int i=1; i<=m; i++)
    {
        int cr=i%2, pv=1-cr;
        for (int j=1; j<=r; j++)
        {
            for (int k=1; k<=c; k++)
            {
                if (mp[j][k]!='#')
                {
                    if (s[i-1]=='?') for (int l=0; l<4; l++) dp[cr][j][k]|=dp[pv][j+dy[l]][k+dx[l]];
                    else dp[cr][j][k]=dp[pv][j+dy[en[s[i-1]]]][k+dx[en[s[i-1]]]];
                }
                if (i==m&&dp[cr][j][k]) cnt++;
            }
        }
        for (int j=1; j<=r; j++) for (int k=1; k<=c; k++) dp[pv][j][k]=0;
    }
    cout<<cnt;
}

Compilation message (stderr)

nautilus.cpp: In function 'int main()':
nautilus.cpp:31:60: warning: array subscript has type 'char' [-Wchar-subscripts]
   31 |                     else dp[cr][j][k]=dp[pv][j+dy[en[s[i-1]]]][k+dx[en[s[i-1]]]];
      |                                                            ^
nautilus.cpp:31:78: warning: array subscript has type 'char' [-Wchar-subscripts]
   31 |                     else dp[cr][j][k]=dp[pv][j+dy[en[s[i-1]]]][k+dx[en[s[i-1]]]];
      |                                                                              ^

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