oj.uz

Submission #927516

# Submission time Handle Problem Language Result Execution time Memory
927516 2024-02-15T02:33:35 Z Faisal_Saqib Nautilus (BOI19_nautilus) C++17
66 / 100
 1000 ms 131480 KB 
#include <iostream>
#include <bitset>
#include <map>
using namespace std;
char g[501][501];
int n,m,M;
string s;
map<char,pair<int,int>> dir;
bitset<5001> pos[501][501];
bitset<5001> fx[501][501];
bool dfs(int x,int y,int ind)
{
  if(x<0 or y<0 or x>=n or y>=m or g[x][y]=='#')
    return 0;
  if(fx[x][y][ind])
    return pos[x][y][ind];
  if(ind==M)
  {
    pos[x][y][ind]=1;
    fx[x][y][ind]=1;
    return 1;   
  }
  if(s[ind]=='?')
  {
    fx[x][y][ind]=1;
    for(auto lp:dir)
      if(dfs(x+lp.second.first,y+lp.second.second,ind+1))
        pos[x][y][ind]=1;
  }
  else
  {
    fx[x][y][ind]=1;
    pos[x][y][ind]=dfs(x+dir[s[ind]].first,y+dir[s[ind]].second,ind+1);   
  }
  return pos[x][y][ind];
}
int main()
{
  dir['N']={-1,0};
  dir['S']={1,0};
  dir['E']={0,1};
  dir['W']={0,-1};
  cin>>n>>m>>M;
  for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
      cin>>g[i][j];
  cin>>s;
  int cnt=0;
  for(int x=0;x<n;x++)
    for(int y=0;y<m;y++)
      dfs(x,y,0);
  for(int x=0;x<n;x++)
    for(int y=0;y<m;y++)
      cnt+=pos[x][y][M];
  cout<<cnt<<endl;
}

Subtask #1
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 13404 KB Output is correct
2 Correct 6 ms 13404 KB Output is correct
3 Correct 6 ms 13404 KB Output is correct
4 Correct 6 ms 12892 KB Output is correct
5 Correct 5 ms 10076 KB Output is correct
6 Correct 2 ms 2648 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 13404 KB Output is correct
2 Correct 6 ms 13404 KB Output is correct
3 Correct 6 ms 13404 KB Output is correct
4 Correct 6 ms 12892 KB Output is correct
5 Correct 5 ms 10076 KB Output is correct
6 Correct 2 ms 2648 KB Output is correct
7 Correct 25 ms 13392 KB Output is correct
8 Correct 11 ms 13404 KB Output is correct
9 Correct 7 ms 14352 KB Output is correct
10 Correct 4 ms 8280 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 36 ms 13404 KB Output is correct
13 Correct 36 ms 37856 KB Output is correct
14 Correct 28 ms 29648 KB Output is correct
15 Correct 5 ms 8284 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 41 ms 39644 KB Output is correct
18 Correct 44 ms 39772 KB Output is correct
19 Correct 18 ms 39328 KB Output is correct
20 Correct 9 ms 36084 KB Output is correct
21 Correct 1 ms 4700 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 13404 KB Output is correct
2 Correct 6 ms 13404 KB Output is correct
3 Correct 6 ms 13404 KB Output is correct
4 Correct 6 ms 12892 KB Output is correct
5 Correct 5 ms 10076 KB Output is correct
6 Correct 2 ms 2648 KB Output is correct
7 Correct 25 ms 13392 KB Output is correct
8 Correct 11 ms 13404 KB Output is correct
9 Correct 7 ms 14352 KB Output is correct
10 Correct 4 ms 8280 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 36 ms 13404 KB Output is correct
13 Correct 36 ms 37856 KB Output is correct
14 Correct 28 ms 29648 KB Output is correct
15 Correct 5 ms 8284 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 41 ms 39644 KB Output is correct
18 Correct 44 ms 39772 KB Output is correct
19 Correct 18 ms 39328 KB Output is correct
20 Correct 9 ms 36084 KB Output is correct
21 Correct 1 ms 4700 KB Output is correct
22 Execution timed out 1055 ms 131480 KB Time limit exceeded
23 Halted 0 ms 0 KB -