Submission #1171438

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171438		akamizane	Nautilus (BOI19_nautilus)	C++20	100 / 100	107 ms	820 KiB

nautilus

#include<bits/stdc++.h>
using namespace std;


#define debug(...) 42


#define int long long
using ll = long long;

const int sz = 505;
const int maxn = 5005;
bitset<sz> dp[2][sz], ok[sz]; 

void solve(){
  int r, c, m;
  cin >> r >> c >> m;
  vector<string> a(r);
  for (auto& x : a) cin >> x;
  for (int i = 0; i < r; i++){
    for (int j = 0; j < c; j++){
      if (a[i][j] == '.'){
        ok[i][j] = 1;
        dp[0][i][j] = 1;
      }
    }
  }
  string s;
  cin >> s;
  for (int i = 1; i <= m; i++){
    auto cur = s[i - 1];
    for (int i = 0; i < r; i++){
      if (cur == 'W' || cur == '?'){
        dp[1][i] |= (dp[0][i] >> 1);
      } 
      if (cur == 'S' || cur == '?'){
        if (i > 0){
          dp[1][i] |= (dp[0][i - 1]);
        }
      }
      if (cur == 'E' || cur == '?'){
        dp[1][i] |= (dp[0][i] << 1);
      }
      if (cur == 'N' || cur == '?'){
        if (i != r - 1) dp[1][i] |= (dp[0][i + 1]);
      }
      dp[1][i] &= ok[i];
    }
    for (int i = 0; i < r; i++){
      dp[0][i] = dp[1][i];
      dp[1][i].reset();
    }
  }
  debug(1);
  int ans = 0;
  for (int i = 0; i < r; i++){
    for (int j = 0; j < c; j++){
      ans += (dp[0][i][j] == 1);
    }
  }
  debug(ans);
  cout << ans;
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int tt = 1;
  // cin >> tt;
  while (tt--){
    solve();
  }
  return 0;
}

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