답안 #927519

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
927519	2024-02-15T02:35:02 Z	Faisal_Saqib	Nautilus (BOI19_nautilus)	C++17	66 / 100	1000 ms	136864 KB

nautilus

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-