Submission #310069

#	Time	Username	Problem	Language	Result	Execution time	Memory
310069		Pety	Nautilus (BOI19_nautilus)	C++14	100 / 100	179 ms	888 KiB

nautilus

#include<bits/stdc++.h>
#define pii pair<int, int>

using namespace std;

typedef long long ll;

int n, m, k;
bitset<502>v[502];
bitset<502>dp[2][502];


int main()
{
  cin >> n >> m >> k;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) {
      char ch;
      cin >> ch;
      if (ch == '.') {
        dp[1][i][j] = 1;
        v[i][j] = 1;
      }
    }
  string s;
  cin >> s;
  for (int ii = 0; ii < k; ii++) {
    for (int j = 1; j <= n;j++) {
      dp[ii % 2][j] = dp[1 - ii % 2][j];
    }
    for (int j = 1; j <= n; j++) {
      if (s[ii] == 'E')
        dp[ii % 2][j] = (dp[1 - ii % 2][j] << 1);
      if (s[ii] == 'W')
        dp[ii % 2][j] = (dp[1 - ii % 2][j] >> 1);
      if (s[ii] == 'N')
        dp[ii % 2][j] = (dp[1 - ii % 2][j + 1]);
      if (s[ii] == 'S')
        dp[ii % 2][j] = (dp[1 - ii % 2][j - 1]);
      if (s[ii] == '?') {
        dp[ii % 2][j] = (dp[1 - ii % 2][j] << 1);
        dp[ii % 2][j] |= (dp[1 - ii % 2][j] >> 1);
        dp[ii % 2][j] |= (dp[1 - ii % 2][j + 1]);
        dp[ii % 2][j] |= (dp[1 - ii % 2][j - 1]);
      }
      dp[ii % 2][j] &= (v[j]);
    }
  }
  int ans = 0;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      ans += dp[(k - 1) % 2][i][j];
  cout << ans;
  return 0;
}

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