Submission #535203

#	Time	Username	Problem	Language	Result	Execution time	Memory
535203		__Variatto	Nautilus (BOI19_nautilus)	C++17	66 / 100	1038 ms	1476 KiB

nautilus

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define ll long long
const int MAX=5e3+10;
int n, m, k;
string curr, s;
bitset<MAX>dp[2][MAX], p[MAX];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1; i<=n; i++){
        cin>>curr;
        for(int j=1; j<=m; j++)
            if(curr[j-1]=='.')
                p[i][j]=dp[1][i][j]=1;
    }
    cin>>s;
    s='$'+s;
    int x=0;
    for(int i=1; i<=k; i++){
        for(int j=1; j<=n; j++)
            dp[x][j]&=0;
        if(s[i]=='?'||s[i]=='E')
            for(int j=1; j<=n; j++)
                dp[x][j]=(dp[x][j]|(dp[!x][j]<<1));
        if(s[i]=='?'||s[i]=='W')
            for(int j=1; j<=n; j++)
                dp[x][j]=(dp[x][j]|(dp[!x][j]>>1));
        if(s[i]=='?'||s[i]=='N')
            for(int j=n-1; j>=1; j--)
                dp[x][j]=(dp[x][j]|dp[!x][j+1]);
        if(s[i]=='?'||s[i]=='S')
            for(int j=2; j<=n; j++)
                dp[x][j]=(dp[x][j]|dp[!x][j-1]);
        for(int j=1; j<=n; j++)
            dp[x][j]&=p[j];
        x=!x;
    }
    int wynik=0;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            wynik+=dp[!x][i][j];
    cout<<wynik<<"\n";
}

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