답안 #927516

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
927516	2024-02-15T02:33:35 Z	Faisal_Saqib	Nautilus (BOI19_nautilus)	C++17	66 / 100	1000 ms	131480 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()
{
  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

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

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

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