oj.uz

Submission #927518

# Submission time Handle Problem Language Result Execution time Memory
927518 2024-02-15T02:34:50 Z Muhammad_Aneeq Nautilus (BOI19_nautilus) C++17
66 / 100
 1000 ms 174684 KB 
/*
بسم الله الرحمن الرحيم
Author:
                          (:Muhammad Aneeq:)
*/

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int r,c,m;
int const R=500+10;
int const M=5000+10;
vector<vector<char>>a(R,vector<char>(R));
string s;
int ans=0;
vector<vector<vector<bool>>>vis(R,vector<vector<bool>>(R,vector<bool>(M)));
queue<pair<int,pair<int,int>>>Q;
inline bool check(int i,int j,int ind)
{
  if (i<0||i>=r||j<0||j>=c||a[i][j]=='#'||vis[i][j][ind])
    return 0;
  Q.push({ind,{i,j}});
  vis[i][j][ind]=1;
  return 1;
}
inline void bfs(int i,int j)
{
  check(i,j,0);
  while (Q.size())
  {
    auto z=Q.front();
    Q.pop();
    int ind=z.first,i=z.second.first,j=z.second.second;
    if (ind==m)
    {
      ans++;
      return;
    }
      if (s[ind]=='?')
    {
      check(i+1,j,ind+1);
      check(i,j+1,ind+1);
      check(i-1,j,ind+1);
      check(i,j-1,ind+1);
    }
    if (s[ind]=='N')
      check(i-1,j,ind+1);
    if (s[ind]=='S')
      check(i+1,j,ind+1);
    if (s[ind]=='E')
      check(i,j+1,ind+1);
    if (s[ind]=='W')
      check(i,j-1,ind+1);
  }
}
inline void solve()
{
  cin>>r>>c>>m;
  for (int i=0;i<r;i++)
    for (int j=0;j<c;j++)
      cin>>a[i][j];
  cin>>s;
  for (int i=0;i<r;i++)
    for (int j=0;j<c;j++)
      bfs(i,j);
  cout<<ans<<endl;
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
        solve();
}

Subtask #1
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 173904 KB Output is correct
2 Correct 157 ms 173936 KB Output is correct
3 Correct 156 ms 173848 KB Output is correct
4 Correct 160 ms 174056 KB Output is correct
5 Correct 160 ms 173956 KB Output is correct
6 Correct 157 ms 174076 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 173904 KB Output is correct
2 Correct 157 ms 173936 KB Output is correct
3 Correct 156 ms 173848 KB Output is correct
4 Correct 160 ms 174056 KB Output is correct
5 Correct 160 ms 173956 KB Output is correct
6 Correct 157 ms 174076 KB Output is correct
7 Correct 173 ms 173908 KB Output is correct
8 Correct 165 ms 173972 KB Output is correct
9 Correct 159 ms 173916 KB Output is correct
10 Correct 156 ms 173892 KB Output is correct
11 Correct 158 ms 173900 KB Output is correct
12 Correct 176 ms 174016 KB Output is correct
13 Correct 180 ms 173928 KB Output is correct
14 Correct 169 ms 173864 KB Output is correct
15 Correct 157 ms 174104 KB Output is correct
16 Correct 160 ms 173908 KB Output is correct
17 Correct 177 ms 173904 KB Output is correct
18 Correct 193 ms 174008 KB Output is correct
19 Correct 163 ms 173908 KB Output is correct
20 Correct 158 ms 173904 KB Output is correct
21 Correct 165 ms 173856 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 173904 KB Output is correct
2 Correct 157 ms 173936 KB Output is correct
3 Correct 156 ms 173848 KB Output is correct
4 Correct 160 ms 174056 KB Output is correct
5 Correct 160 ms 173956 KB Output is correct
6 Correct 157 ms 174076 KB Output is correct
7 Correct 173 ms 173908 KB Output is correct
8 Correct 165 ms 173972 KB Output is correct
9 Correct 159 ms 173916 KB Output is correct
10 Correct 156 ms 173892 KB Output is correct
11 Correct 158 ms 173900 KB Output is correct
12 Correct 176 ms 174016 KB Output is correct
13 Correct 180 ms 173928 KB Output is correct
14 Correct 169 ms 173864 KB Output is correct
15 Correct 157 ms 174104 KB Output is correct
16 Correct 160 ms 173908 KB Output is correct
17 Correct 177 ms 173904 KB Output is correct
18 Correct 193 ms 174008 KB Output is correct
19 Correct 163 ms 173908 KB Output is correct
20 Correct 158 ms 173904 KB Output is correct
21 Correct 165 ms 173856 KB Output is correct
22 Execution timed out 1068 ms 174684 KB Time limit exceeded
23 Halted 0 ms 0 KB -