Submission #1010737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010737		alexdd	Nautilus (BOI19_nautilus)	C++17	100 / 100	156 ms	756 KiB

nautilus

#include<bits/stdc++.h>
using namespace std;
bitset<505> dp[2][505];
bitset<505> mat[505];
bitset<505> emp;
int n,m,L,p;
void baga_N()
{
    for(int i=1;i<n;i++)
        dp[p][i] |= dp[1-p][i+1];
}
void baga_S()
{
    for(int i=2;i<=n;i++)
        dp[p][i] |= dp[1-p][i-1];
}
void baga_E()
{
    for(int i=1;i<=n;i++)
    {
        bool inainte = dp[p][i][1];
        dp[p][i] |= (dp[1-p][i]<<1);
        dp[p][i][1] = inainte;
    }
}
void baga_W()
{
    for(int i=1;i<=n;i++)
    {
        bool inainte = dp[p][i][m];
        dp[p][i] |= (dp[1-p][i]>>1);
        dp[p][i][m] = inainte;
    }
}
signed main()
{
    cin>>n>>m>>L;
    char ch;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>ch;
            if(ch=='#')
            {
                mat[i][j]=0;
            }
            else
            {
                mat[i][j]=1;
                dp[0][i][j]=1;
            }
        }
    }
    for(int pas=1;pas<=L;pas++)
    {
        p = 1-p;
        cin>>ch;
        for(int i=1;i<=n;i++)
            dp[p][i]=emp;
        if(ch=='?')
        {
            baga_N();
            baga_E();
            baga_S();
            baga_W();
        }
        else if(ch=='N') baga_N();
        else if(ch=='S') baga_S();
        else if(ch=='E') baga_E();
        else baga_W();

        for(int i=1;i<=n;i++)
            dp[p][i] = (dp[p][i] & mat[i]);
    }
    int cnt=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(dp[p][i][j])
                cnt++;
    cout<<cnt;
    return 0;
}

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