oj.uz

Submission #648685

# Submission time Handle Problem Language Result Execution time Memory
648685 2022-10-07T13:23:34 Z alvinpiter Nautilus (BOI19_nautilus) C++17
66 / 100
 207 ms 158180 KB 
/*
dp[r][c][idx] -> Is it possible to reach cell (r, c) after executing idx-th command. idx starts from 1.

Base case:
dp[r][c][0] = 1 if isWater(r, c), 0 otherwise.

Transition:
command[idx] = 'N' -> dp[r][c][idx] = dp[r + 1][c][idx - 1] && isWater(r, c)
command[idx] = 'E' -> dp[r][c][idx] = dp[r][c - 1][idx - 1] && isWater(r, c)
command[idx] = 'S' -> dp[r][c][idx] = dp[r - 1][c][idx - 1] && isWater(r, c)
command[idx] = 'W' -> dp[r][c][idx] = dp[r][c + 1][idx - 1] && isWater(r, c)
command[idx] = '?' -> dp[r][c][idx] = (OR of the above) && isWater(r, c)

Naive implementation will get TLE/MLE, because there are R*C*M states. We need C++'s bitset.

isWater(r) -> a bitset that represents whether a certain column in row r is filled with water.
dp[r][idx] -> a bitset that represents whether a certain column in row r can be reached after executing idx-th command.

command[idx] = 'N' -> dp[r][idx] = dp[r + 1][idx - 1] && isWater(r)
command[idx] = 'E' -> dp[r][idx] = (dp[r][idx - 1]) << 1) && isWater(r)
command[idx] = 'S' -> dp[r][idx] = dp[r - 1][idx - 1] && isWater(r)
command[idx] = 'W' -> dp[r][idx] = (dp[r][idx - 1] >> 1) && isWater(r)
command[idx] = '?' -> dp[r][idx] = (OR of the above) && isWater(r)

Notice the direction of the left shift and right shift. It is reversed because the bitset is indexed starting from 0
from the right.
*/

#include<bits/stdc++.h>
using namespace std;
#define MAXR 500
#define MAXM 5000

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

  int R, C, M;
  string command;

  cin >> R >> C >> M;

  bitset<MAXR + 3> isWater[R + 3], dp[R + 3][MAXM + 3];

  for (int r = 0; r < R; r++) {
    for (int c = 0; c < C; c++) {
      char cell;
      cin >> cell;

      if (cell == '.') {
        isWater[r].set(c, 1);
        dp[r][0].set(c, 1);
      }
    }
  }

  cin >> command;

  for (int idx = 1; idx <= M; idx++) {
    for (int r = 0; r < R; r++) {
      switch (command[idx - 1]) {
        case 'N':
          dp[r][idx] = dp[r + 1][idx - 1] & isWater[r];
          break;
        case 'E':
          dp[r][idx] = (dp[r][idx - 1] << 1) & isWater[r];
          break;
        case 'S':
          dp[r][idx] = dp[r - 1][idx - 1] & isWater[r];
          break;
        case 'W':
          dp[r][idx] = (dp[r][idx - 1] >> 1) & isWater[r];
          break;
        case '?':
          dp[r][idx] = (dp[r + 1][idx - 1] | (dp[r][idx - 1] << 1) | dp[r - 1][idx - 1] | (dp[r][idx - 1] >> 1)) & isWater[r];
          break;
      }
    }
  }

  int ans = 0;
  for (int r = 0; r < R; r++) {
    for (int c = 0; c < C; c++) {
      if (dp[r][M].test(c)) {
        ans += 1;
      }
    }
  }

  cout << ans << endl;
}

Subtask #1
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 32516 KB Output is correct
2 Correct 20 ms 32596 KB Output is correct
3 Correct 19 ms 32560 KB Output is correct
4 Correct 23 ms 32584 KB Output is correct
5 Correct 19 ms 32604 KB Output is correct
6 Correct 21 ms 32584 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 32516 KB Output is correct
2 Correct 20 ms 32596 KB Output is correct
3 Correct 19 ms 32560 KB Output is correct
4 Correct 23 ms 32584 KB Output is correct
5 Correct 19 ms 32604 KB Output is correct
6 Correct 21 ms 32584 KB Output is correct
7 Correct 17 ms 32596 KB Output is correct
8 Correct 19 ms 32576 KB Output is correct
9 Correct 18 ms 32600 KB Output is correct
10 Correct 20 ms 32524 KB Output is correct
11 Correct 21 ms 32480 KB Output is correct
12 Correct 21 ms 32524 KB Output is correct
13 Correct 20 ms 32596 KB Output is correct
14 Correct 18 ms 32596 KB Output is correct
15 Correct 18 ms 32596 KB Output is correct
16 Correct 19 ms 32596 KB Output is correct
17 Correct 17 ms 32596 KB Output is correct
18 Correct 18 ms 32600 KB Output is correct
19 Correct 20 ms 32564 KB Output is correct
20 Correct 17 ms 32604 KB Output is correct
21 Correct 18 ms 32628 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 32516 KB Output is correct
2 Correct 20 ms 32596 KB Output is correct
3 Correct 19 ms 32560 KB Output is correct
4 Correct 23 ms 32584 KB Output is correct
5 Correct 19 ms 32604 KB Output is correct
6 Correct 21 ms 32584 KB Output is correct
7 Correct 17 ms 32596 KB Output is correct
8 Correct 19 ms 32576 KB Output is correct
9 Correct 18 ms 32600 KB Output is correct
10 Correct 20 ms 32524 KB Output is correct
11 Correct 21 ms 32480 KB Output is correct
12 Correct 21 ms 32524 KB Output is correct
13 Correct 20 ms 32596 KB Output is correct
14 Correct 18 ms 32596 KB Output is correct
15 Correct 18 ms 32596 KB Output is correct
16 Correct 19 ms 32596 KB Output is correct
17 Correct 17 ms 32596 KB Output is correct
18 Correct 18 ms 32600 KB Output is correct
19 Correct 20 ms 32564 KB Output is correct
20 Correct 17 ms 32604 KB Output is correct
21 Correct 18 ms 32628 KB Output is correct
22 Correct 207 ms 158180 KB Output is correct
23 Incorrect 171 ms 158176 KB Output isn't correct
24 Halted 0 ms 0 KB -