Submission #920737

#	Time	Username	Problem	Language	Result	Execution time	Memory
920737		12345678	Nautilus (BOI19_nautilus)	C++17	100 / 100	186 ms	1104 KiB

nautilus

#include <bits/stdc++.h>

using namespace std;

const int nx=505;
int r, c, m, cnt;
char mp[nx][nx];
bitset<nx> dp[2][nx], w[nx];
string s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>r>>c>>m;
    for (int i=1; i<=r; i++) for (int j=1; j<=c; j++) cin>>mp[i][j], w[i][j]=(mp[i][j]!='#'), dp[0][i][j]=w[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++) dp[cr][j]=0;
        if (s[i-1]=='N'||s[i-1]=='?') for (int j=1; j<=r-1; j++) dp[cr][j]|=dp[pv][j+1];
        if (s[i-1]=='S'||s[i-1]=='?') for (int j=2; j<=r; j++) dp[cr][j]|=dp[pv][j-1];
        if (s[i-1]=='E'||s[i-1]=='?') for (int j=1; j<=r; j++) dp[cr][j]|=dp[pv][j]<<1;
        if (s[i-1]=='W'||s[i-1]=='?') for (int j=1; j<=r; j++) dp[cr][j]|=dp[pv][j]>>1;
        for (int j=1; j<=r; j++) dp[cr][j]&=w[j];
    }
    for (int i=1; i<=r; i++) for (int j=1; j<=c; j++) cnt+=dp[m%2][i][j];
    cout<<cnt;
}

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