oj.uz

Submission #210628

# Submission time Handle Problem Language Result Execution time Memory
210628 2020-03-17T23:54:40 Z casperwang Nautilus (BOI19_nautilus) C++14
29 / 100
 10 ms 764 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500;
int r, c, m;
int dx, dy;
int cnt;
string str;
string mp[MAXN+5];
int dp[MAXN+5][MAXN+5][2];

signed main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  cin >> r >> c >> m;
  for (int i = 1; i <= r; i++) {
    cin >> mp[i];
    mp[i] = "#" + mp[i] + "#";
  }
  cin >> str;
  for (int i = 0; i <= c+1; i++) {
    mp[0] = mp[0] + "#";
    mp[r+1] = mp[r+1] + "#";
  }
  for (int i = 1; i <= r; i++)
    for (int j = 1; j <= c; j++)
      dp[i][j][1] = (mp[i][j] != '#');
  for (int k = 0; k < m; k++) {
    if (str[k] == 'S') dx = -1, dy = 0;
    if (str[k] == 'N') dx = 1, dy = 0;
    if (str[k] == 'E') dx = 0, dy = -1;
    if (str[k] == 'W') dx = 0, dy = 1;
    for (int i = 1; i <= r; i++)
      for (int j = 1; j <= c; j++)
        dp[i][j][k%2] = (mp[i][j] != '#') * (dp[i+dx][j+dy][(k+1)%2]);
    if (str[k] != '?') continue;
    for (int i = 1; i <= r; i++) {
      for (int j = 1; j <= c; j++) {
        dp[i][j][k%2] |= (mp[i][j] != '#') * (dp[i][j+1][(k+1)%2]);
        dp[i][j][k%2] |= (mp[i][j] != '#') * (dp[i][j-1][(k+1)%2]);
        dp[i][j][k%2] |= (mp[i][j] != '#') * (dp[i+1][j][(k+1)%2]);
        dp[i][j][k%2] |= (mp[i][j] != '#') * (dp[i-1][j][(k+1)%2]);
      }
    }
  }
  for (int i = 1; i <= r; i++)
    for (int j = 1; j <= c; j++)
      cnt += dp[i][j][(m+1)%2];
  cout << cnt << "\n";
}

Subtask #1
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 760 KB Output is correct
2 Correct 6 ms 760 KB Output is correct
3 Correct 6 ms 760 KB Output is correct
4 Correct 6 ms 760 KB Output is correct
5 Correct 6 ms 760 KB Output is correct
6 Correct 6 ms 760 KB Output is correct

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 760 KB Output is correct
2 Correct 6 ms 760 KB Output is correct
3 Correct 6 ms 760 KB Output is correct
4 Correct 6 ms 760 KB Output is correct
5 Correct 6 ms 760 KB Output is correct
6 Correct 6 ms 760 KB Output is correct
7 Correct 8 ms 764 KB Output is correct
8 Correct 8 ms 760 KB Output is correct
9 Correct 7 ms 760 KB Output is correct
10 Correct 8 ms 632 KB Output is correct
11 Correct 7 ms 760 KB Output is correct
12 Correct 9 ms 760 KB Output is correct
13 Correct 9 ms 760 KB Output is correct
14 Correct 9 ms 760 KB Output is correct
15 Correct 9 ms 760 KB Output is correct
16 Correct 9 ms 764 KB Output is correct
17 Correct 10 ms 760 KB Output is correct
18 Incorrect 10 ms 760 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 760 KB Output is correct
2 Correct 6 ms 760 KB Output is correct
3 Correct 6 ms 760 KB Output is correct
4 Correct 6 ms 760 KB Output is correct
5 Correct 6 ms 760 KB Output is correct
6 Correct 6 ms 760 KB Output is correct
7 Correct 8 ms 764 KB Output is correct
8 Correct 8 ms 760 KB Output is correct
9 Correct 7 ms 760 KB Output is correct
10 Correct 8 ms 632 KB Output is correct
11 Correct 7 ms 760 KB Output is correct
12 Correct 9 ms 760 KB Output is correct
13 Correct 9 ms 760 KB Output is correct
14 Correct 9 ms 760 KB Output is correct
15 Correct 9 ms 760 KB Output is correct
16 Correct 9 ms 764 KB Output is correct
17 Correct 10 ms 760 KB Output is correct
18 Incorrect 10 ms 760 KB Output isn't correct
19 Halted 0 ms 0 KB -