Submission #655872

#	Time	Username	Problem	Language	Result	Execution time	Memory
655872		600Mihnea	Nautilus (BOI19_nautilus)	C++17	100 / 100	140 ms	672 KiB

nautilus

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")

using namespace std;

typedef long long ll;

const int N = 500 + 7;
int n;
int m;
int sdim;
bitset<N> valid_place[N];
bitset<N> ok[N];
bitset<N> nok[N];
string s;

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> m >> sdim;
  for (int i = 1; i <= n; i++) {
    string s;
    cin >> s;
    for (int j = 1; j <= m; j++) {
      char ch = s[j - 1];
      valid_place[i][j] = (ch == '.');
    }
  }
  cin >> s;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      ok[i][j] = valid_place[i][j];
    }
  }
  for (int itp = 0; itp < sdim; itp++) {
    char ch = s[itp];
    for (int i = 1; i <= n; i++) {
      nok[i] = 0;
    }
    if (ch == 'N' || ch == '?') {
      for (int i = 1; i <= n; i++) {
        nok[i] |= ok[i + 1];
      }
    }
    if (ch == 'S' || ch == '?') {
      for (int i = 1; i <= n; i++) {
        nok[i] |= ok[i - 1];
      }
    }
    if (ch == 'E' || ch == '?') {
      for (int i = 1; i <= n; i++) {
        nok[i] |= (ok[i] << 1);
      }
    }
    if (ch == 'W' || ch == '?') {
      for (int i = 1; i <= n; i++) {
        nok[i] |= (ok[i] >> 1);
      }
    }
    for (int i = 1; i <= n; i++) {
      ok[i] = nok[i] & valid_place[i];
    }
  }
  int sol = 0;
  for (int i = 1; i <= n; i++) {
    sol += ok[i].count();
  }
  cout << sol << "\n";
  return 0;
}


/**

**/

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