oj.uz

Submission #648698

# Submission time Handle Problem Language Result Execution time Memory
648698 2022-10-07T13:47:41 Z alvinpiter Nautilus (BOI19_nautilus) C++17
66 / 100
 187 ms 157924 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] = (d[r + 1][c][idx - 1] & 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] = (dp[r + 1][idx - 1] && 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] & isWater[r]) | ((dp[r][idx - 1] << 1) & isWater[r]) | (dp[r - 1][idx - 1] & isWater[r]) | ((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 19 ms 32468 KB Output is correct
2 Correct 21 ms 32596 KB Output is correct
3 Correct 18 ms 32544 KB Output is correct
4 Correct 18 ms 32596 KB Output is correct
5 Correct 18 ms 32548 KB Output is correct
6 Correct 18 ms 32588 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 32468 KB Output is correct
2 Correct 21 ms 32596 KB Output is correct
3 Correct 18 ms 32544 KB Output is correct
4 Correct 18 ms 32596 KB Output is correct
5 Correct 18 ms 32548 KB Output is correct
6 Correct 18 ms 32588 KB Output is correct
7 Correct 18 ms 32596 KB Output is correct
8 Correct 19 ms 32544 KB Output is correct
9 Correct 19 ms 32580 KB Output is correct
10 Correct 18 ms 32588 KB Output is correct
11 Correct 21 ms 32596 KB Output is correct
12 Correct 21 ms 32592 KB Output is correct
13 Correct 19 ms 32536 KB Output is correct
14 Correct 18 ms 32468 KB Output is correct
15 Correct 18 ms 32592 KB Output is correct
16 Correct 17 ms 32600 KB Output is correct
17 Correct 21 ms 32540 KB Output is correct
18 Correct 18 ms 32468 KB Output is correct
19 Correct 18 ms 32588 KB Output is correct
20 Correct 18 ms 32496 KB Output is correct
21 Correct 19 ms 32596 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 32468 KB Output is correct
2 Correct 21 ms 32596 KB Output is correct
3 Correct 18 ms 32544 KB Output is correct
4 Correct 18 ms 32596 KB Output is correct
5 Correct 18 ms 32548 KB Output is correct
6 Correct 18 ms 32588 KB Output is correct
7 Correct 18 ms 32596 KB Output is correct
8 Correct 19 ms 32544 KB Output is correct
9 Correct 19 ms 32580 KB Output is correct
10 Correct 18 ms 32588 KB Output is correct
11 Correct 21 ms 32596 KB Output is correct
12 Correct 21 ms 32592 KB Output is correct
13 Correct 19 ms 32536 KB Output is correct
14 Correct 18 ms 32468 KB Output is correct
15 Correct 18 ms 32592 KB Output is correct
16 Correct 17 ms 32600 KB Output is correct
17 Correct 21 ms 32540 KB Output is correct
18 Correct 18 ms 32468 KB Output is correct
19 Correct 18 ms 32588 KB Output is correct
20 Correct 18 ms 32496 KB Output is correct
21 Correct 19 ms 32596 KB Output is correct
22 Correct 187 ms 157924 KB Output is correct
23 Incorrect 168 ms 157904 KB Output isn't correct
24 Halted 0 ms 0 KB -