Submission #1171737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171737		AlgorithmWarrior	Nautilus (BOI19_nautilus)	C++20	100 / 100	202 ms	1288 KiB

nautilus

#include <bits/stdc++.h>

using namespace std;

int n,m,sz;
char sir[5005],mat[505][505];
bitset<250005>dp,ok,up,down,lft,rght;

void read(){
    cin>>n>>m>>sz;
    int i,j;
    for(i=0;i<n;++i)
        for(j=0;j<m;++j){
            cin>>mat[i][j];
            if(mat[i][j]=='.')
                ok[i*m+j]=1;
            if(i>0)
                up[i*m+j]=1;
            if(i<n-1)
                down[i*m+j]=1;
            if(j>0)
                lft[i*m+j]=1;
            if(j<m-1)
                rght[i*m+j]=1;
        }
    for(i=0;i<sz;++i)
        cin>>sir[i];
}

int get_dp(){
    dp=ok;
    int i;
    for(i=0;i<sz;++i){
        if(sir[i]=='N')
            dp=(((dp&up)>>m)&ok);
        if(sir[i]=='S')
            dp=(((dp&down)<<m)&ok);
        if(sir[i]=='W')
            dp=(((dp&lft)>>1)&ok);
        if(sir[i]=='E')
            dp=(((dp&rght)<<1)&ok);
        if(sir[i]=='?')
            dp=((((dp&up)>>m)|((dp&down)<<m)|((dp&lft)>>1)|((dp&rght)<<1))&ok);
    }
    return dp.count();
}

int main()
{
    read();
    cout<<get_dp();
    return 0;
}

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