Submission #221382

#	Time	Username	Problem	Language	Result	Execution time	Memory
221382		Leonardo_Paes	Nautilus (BOI19_nautilus)	C++17	100 / 100	59 ms	512 KiB

nautilus

#include <bits/stdc++.h>

using namespace std;

#pragma GCC optimize("Ofast")

const int maxn = 510;

int r, c, m, ans = 0;

bitset<maxn> dp[maxn], mat[maxn], tfg[maxn];

string s;

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

    cin >> r >> c >> m;

    for(int i=0; i<r; i++){
        for(int j=0; j<c; j++){
            char a;
            cin >> a;
            if(a == '.') mat[i][c-j-1] = dp[i][c-j-1] = 1;
        }
    }

    cin >> s;

    for(int j=0; j<s.size(); j++){
        if(s[j] == 'N'){
            for(int i=0; i<r; i++){
                if(i+1 < r) dp[i] = (dp[i+1] & mat[i]);
                else dp[i].reset();
            }
        }
        if(s[j] == 'S'){
            for(int i=r-1; i>=0; i--){
                if(i) dp[i] = (dp[i-1] & mat[i]);
                else dp[i].reset();
            }
        }
        if(s[j] == 'E'){
            for(int i=0; i<r; i++){
                dp[i] = ((dp[i] >> 1) & mat[i]);
            }
        }
        if(s[j] == 'W'){
            for(int i=0; i<r; i++){
                dp[i] = ((dp[i] << 1) & mat[i]);
            }
        }
        if(s[j] == '?'){
            for(int i=0; i<r; i++){
                tfg[i] = (dp[i] << 1)|(dp[i] >> 1);
                if(i) tfg[i] |= dp[i-1];
                if(i+1 < r) tfg[i] |= dp[i+1];
                tfg[i] &= mat[i];
            }
            for(int i=0; i<r; i++){
                dp[i] = tfg[i];
            }
        }
    }

    for(int i=0; i<r; i++) ans += dp[i].count();

    cout << ans << endl;

    return 0;
}

Compilation message (stderr)

nautilus.cpp: In function 'int main()':
nautilus.cpp:30:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0; j<s.size(); j++){
                  ~^~~~~~~~~

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