Submission #951165

#	Time	Username	Problem	Language	Result	Execution time	Memory
951165		LOLOLO	Nautilus (BOI19_nautilus)	C++17	100 / 100	72 ms	159280 KiB

nautilus

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
typedef long long ll;
char mat[505][505];
bitset<505> is[505],dp[5005][505];
int main(){
    std::ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    int r,c,m;
    cin>>r>>c>>m;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            cin>>mat[i][j];
            is[i][j]=(mat[i][j]=='.');
            dp[0][i][j]=is[i][j];
        }
    }

    string s;
    cin>>s;
    s='a'+s;

    for(int t=1;t<=m;t++){
        for(int i=1;i<=r;i++){
            if(s[t]=='?')
                dp[t][i]=(dp[t-1][i+1]|dp[t-1][i-1]|(dp[t-1][i]<<1)|(dp[t-1][i]>>1))&is[i];
            if(s[t]=='N')
                dp[t][i]=dp[t-1][i+1]&is[i];
            if(s[t]=='S')
                dp[t][i]=dp[t-1][i-1]&is[i];
            if(s[t]=='E')
                dp[t][i]=(dp[t-1][i]<<1)&is[i];
            if(s[t]=='W')
                dp[t][i]=(dp[t-1][i]>>1)&is[i];
        }
    }

    int cnt=0;

    for(int i=1;i<=r;i++){
        cnt+=dp[m][i].count();
    }

    cout<<cnt<<endl;
}

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