oj.uz

Submission #1021863

# Submission time Handle Problem Language Result Execution time Memory
1021863 2024-07-13T06:25:12 Z basa Nautilus (BOI19_nautilus) C++14
29 / 100
 1000 ms 79448 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
string m;
int r, c, k;
string s[505];
map<array<int, 3>, bool>vis;
 
int dfs(int i, int j, int p){
  if(i >= r || i < 0) return 0;
  if(j >= c || j < 0) return 0;
  if(s[i][j] == '#') return 0;
  if(vis[{i, j, p}]) return 0;
  vis[{i, j, p}] = 1;
  if(p == m.size()) return 1;
 
 
  int ret = 0;
 
  if(m[p] == 'N') ret = dfs(i - 1, j, p + 1);
  if(m[p] == 'S') ret = dfs(i + 1, j, p + 1);
  if(m[p] == 'E') ret = dfs(i, j + 1, p + 1);
  if(m[p] == 'W') ret = dfs(i, j - 1, p + 1);
 
  if(m[p] == '?'){
    ret += dfs(i + 1, j, p + 1);
    ret += dfs(i - 1, j, p + 1);
    ret += dfs(i, j + 1, p + 1);
    ret += dfs(i, j - 1, p + 1);
  }
 
  return ret;
}
 
signed main()
{
  cin.tie(0) -> sync_with_stdio(0);
  cin >> r >> c >> k;
 
  for(int i = 0; i < r; i++) cin >> s[i];
 
  cin >> m;
 
  int ans = 0;
  for(int i = 0; i < r; i++){
    for(int j = 0; j < c; j++){
      if(s[i][j] == '#') continue;
      ans += dfs(i, j, 0);
    }
  }
 
  cout << ans;
}

Compilation message

nautilus.cpp: In function 'long long int dfs(long long int, long long int, long long int)':
nautilus.cpp:18:8: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |   if(p == m.size()) return 1;
      |      ~~^~~~~~~~~~~

Subtask #1
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 70480 KB Output is correct
2 Correct 18 ms 4952 KB Output is correct
3 Correct 7 ms 1624 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 70480 KB Output is correct
2 Correct 18 ms 4952 KB Output is correct
3 Correct 7 ms 1624 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 537 ms 77584 KB Output is correct
8 Correct 68 ms 14164 KB Output is correct
9 Correct 14 ms 3676 KB Output is correct
10 Correct 4 ms 1372 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 805 ms 78956 KB Output is correct
13 Correct 478 ms 58448 KB Output is correct
14 Correct 225 ms 36696 KB Output is correct
15 Correct 9 ms 2392 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Execution timed out 1033 ms 79448 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 70480 KB Output is correct
2 Correct 18 ms 4952 KB Output is correct
3 Correct 7 ms 1624 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 537 ms 77584 KB Output is correct
8 Correct 68 ms 14164 KB Output is correct
9 Correct 14 ms 3676 KB Output is correct
10 Correct 4 ms 1372 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 805 ms 78956 KB Output is correct
13 Correct 478 ms 58448 KB Output is correct
14 Correct 225 ms 36696 KB Output is correct
15 Correct 9 ms 2392 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Execution timed out 1033 ms 79448 KB Time limit exceeded
18 Halted 0 ms 0 KB -