Submission #679569

#	Time	Username	Problem	Language	Result	Execution time	Memory
679569		lam	Nautilus (BOI19_nautilus)	C++14	100 / 100	215 ms	160172 KiB

nautilus

#include <bits/stdc++.h>
using namespace std;
const int maxn = 510;
const int maxm = 50010;
bitset<500> a[maxn],dp[maxm][maxn];
int n,m,L;
void E(int id)
{
    for (int i=1; i<=n; i++)
        dp[id][i]|=(dp[id-1][i]<<1);
}
void W(int id)
{
    for (int i=1; i<=n; i++)
        dp[id][i]|=(dp[id-1][i]>>1);
}
void N(int id)
{
    for (int i=1; i<n; i++)
        dp[id][i]|=(dp[id-1][i+1]);
}
void S(int id)
{
    for (int i=2; i<=n; i++)
        dp[id][i]|=(dp[id-1][i-1]);
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin>>n>>m>>L;
    for (int i=1; i<=n; i++)
        for (int j=1; j<=m; j++)
    {
        char c; cin>>c;
        if (c=='.') a[i].set(j-1,1), dp[0][i].set(j-1,1);
    }
    for (int i=1; i<=L; i++)
    {
        char c; cin>>c;
        if (c=='N') N(i);
        else if (c=='S') S(i);
        else if (c=='W') W(i);
        else if (c=='E') E(i);
        else
        {
            N(i);
            S(i);
            W(i);
            E(i);
        }
        for (int j=1; j<=n; j++) dp[i][j]&=a[j];
    }
    int ans=0;
    for (int i=1; i<=n; i++)
        for (int j=0; j<m; j++) ans+=dp[L][i][j];
    cout<<ans;

}
/**
5 9 7
...##....
..#.##..#
..#....##
.##...#..
....#....
WS?EE??
**/

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