Submission #123238

#	Time	Username	Problem	Language	Result	Execution time	Memory
123238		miguel	Nautilus (BOI19_nautilus)	C++14	100 / 100	194 ms	157408 KiB

nautilus

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define sz size()
#define x first
#define y second
#define pi pair <int, int>
#define pii pair <pi, int>
#define vi vector <int>
const ll mod = 1000000007;
//#define int ll
int n, m, ss, ans;
set <pi> mp;
bitset<501> t[501];
bitset<501> dp[5002][501];
string s;

bool valid(int x, int y){
    if(x>0 && x<=n && y>0 && y<=m && t[x][y]) return 1;
    else return 0;
}

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    cin>>n>>m>>ss;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            char c;
            cin>>c;
            if(c=='.') t[i][j]=1, dp[0][i][j]=1;
        }
    }
    cin>>s;
    for(int cur=0; cur<ss; cur++){
        for(int i=1; i<=n; i++){
            int x=i;
            char c=s[cur];
            if(c=='?'){
                dp[cur+1][x+1]|=(dp[cur][x]&t[x+1]);
                dp[cur+1][x]|=((dp[cur][x]<<1)&t[x]);
                dp[cur+1][x-1]|=(dp[cur][x]&t[x-1]);
                dp[cur+1][x]|=((dp[cur][x]>>1)&t[x]);
            }
            else if(c=='S'){
                dp[cur+1][x+1]|=(dp[cur][x]&t[x+1]);
            }
            else if(c=='E'){
                dp[cur+1][x]|=((dp[cur][x]<<1)&t[x]);
            }
            else if(c=='N'){
                dp[cur+1][x-1]|=(dp[cur][x]&t[x-1]);
            }
            else if(c=='W'){
                dp[cur+1][x]|=((dp[cur][x]>>1)&t[x]);
            }
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(dp[ss][i][j]) ans++;
        }
    }
    cout<<ans;
}

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