oj.uz

Submission #927519

# Submission time Handle Problem Language Result Execution time Memory
927519 2024-02-15T02:35:02 Z Faisal_Saqib Nautilus (BOI19_nautilus) C++17
66 / 100
 1000 ms 136864 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()
{
  cin.tie(0);
  cout.tie(0);
  ios::sync_with_stdio(0);
  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<<'\n';
}

Subtask #1
29.0 / 29.0

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

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 13660 KB Output is correct
2 Correct 7 ms 13388 KB Output is correct
3 Correct 6 ms 13404 KB Output is correct
4 Correct 5 ms 12892 KB Output is correct
5 Correct 4 ms 10076 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 25 ms 13544 KB Output is correct
8 Correct 11 ms 13404 KB Output is correct
9 Correct 7 ms 14424 KB Output is correct
10 Correct 4 ms 8284 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 35 ms 13400 KB Output is correct
13 Correct 39 ms 37968 KB Output is correct
14 Correct 29 ms 30056 KB Output is correct
15 Correct 4 ms 8280 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 44 ms 39760 KB Output is correct
18 Correct 38 ms 39772 KB Output is correct
19 Correct 16 ms 39260 KB Output is correct
20 Correct 9 ms 36184 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 13660 KB Output is correct
2 Correct 7 ms 13388 KB Output is correct
3 Correct 6 ms 13404 KB Output is correct
4 Correct 5 ms 12892 KB Output is correct
5 Correct 4 ms 10076 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 25 ms 13544 KB Output is correct
8 Correct 11 ms 13404 KB Output is correct
9 Correct 7 ms 14424 KB Output is correct
10 Correct 4 ms 8284 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 35 ms 13400 KB Output is correct
13 Correct 39 ms 37968 KB Output is correct
14 Correct 29 ms 30056 KB Output is correct
15 Correct 4 ms 8280 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 44 ms 39760 KB Output is correct
18 Correct 38 ms 39772 KB Output is correct
19 Correct 16 ms 39260 KB Output is correct
20 Correct 9 ms 36184 KB Output is correct
21 Correct 1 ms 4700 KB Output is correct
22 Execution timed out 1101 ms 136864 KB Time limit exceeded
23 Halted 0 ms 0 KB -