답안 #526213

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
526213	2022-02-14T00:43:07 Z	Yazan_Alattar	Nautilus (BOI19_nautilus)	C++14	66 / 100	1000 ms	4760 KB

nautilus

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 505;
const ll inf = 2e9;
const ll mod = 998244353;
const double pi = acos(-1);
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
const char dirs[] = {'S', 'E', 'N', 'W'};

vector < vector <ll> > dp(M, vector <ll> (M));
ll n, m, ans, len;
string s;
char a[M][M];

int main()
{
	cin >> n >> m >> len;
	for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) cin >> a[i][j], dp[i][j] = 1;
	cin >> s;
	for(int idx = 0; idx < len; ++idx){
		vector < vector <ll> > to(M, vector <ll> (M));
		for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) if(a[i][j] != '#')
			for(int dir = 0; dir < 4; ++dir) if(s[idx] == '?' || s[idx] == dirs[dir])
				to[i + dx[dir]][j + dy[dir]] |= dp[i][j];
		dp = to;
	}
	for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) if(a[i][j] != '#') ans += dp[i][j];
	cout << ans << endl;
	return 0;
}

Subtask #1

29.0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	77 ms	4560 KB	Output is correct
2	Correct	75 ms	4528 KB	Output is correct
3	Correct	81 ms	4496 KB	Output is correct
4	Correct	77 ms	4484 KB	Output is correct
5	Correct	77 ms	4552 KB	Output is correct
6	Correct	66 ms	4576 KB	Output is correct

Subtask #2

37.0 / 37.0

#	결과	실행 시간	메모리	Grader output
1	Correct	77 ms	4560 KB	Output is correct
2	Correct	75 ms	4528 KB	Output is correct
3	Correct	81 ms	4496 KB	Output is correct
4	Correct	77 ms	4484 KB	Output is correct
5	Correct	77 ms	4552 KB	Output is correct
6	Correct	66 ms	4576 KB	Output is correct
7	Correct	80 ms	4456 KB	Output is correct
8	Correct	81 ms	4604 KB	Output is correct
9	Correct	84 ms	4672 KB	Output is correct
10	Correct	79 ms	4564 KB	Output is correct
11	Correct	68 ms	4520 KB	Output is correct
12	Correct	87 ms	4468 KB	Output is correct
13	Correct	86 ms	4520 KB	Output is correct
14	Correct	100 ms	4572 KB	Output is correct
15	Correct	75 ms	4544 KB	Output is correct
16	Correct	73 ms	4500 KB	Output is correct
17	Correct	93 ms	4516 KB	Output is correct
18	Correct	91 ms	4372 KB	Output is correct
19	Correct	85 ms	4508 KB	Output is correct
20	Correct	78 ms	4544 KB	Output is correct
21	Correct	68 ms	4500 KB	Output is correct

Subtask #3

0 / 34.0

#	결과	실행 시간	메모리	Grader output
1	Correct	77 ms	4560 KB	Output is correct
2	Correct	75 ms	4528 KB	Output is correct
3	Correct	81 ms	4496 KB	Output is correct
4	Correct	77 ms	4484 KB	Output is correct
5	Correct	77 ms	4552 KB	Output is correct
6	Correct	66 ms	4576 KB	Output is correct
7	Correct	80 ms	4456 KB	Output is correct
8	Correct	81 ms	4604 KB	Output is correct
9	Correct	84 ms	4672 KB	Output is correct
10	Correct	79 ms	4564 KB	Output is correct
11	Correct	68 ms	4520 KB	Output is correct
12	Correct	87 ms	4468 KB	Output is correct
13	Correct	86 ms	4520 KB	Output is correct
14	Correct	100 ms	4572 KB	Output is correct
15	Correct	75 ms	4544 KB	Output is correct
16	Correct	73 ms	4500 KB	Output is correct
17	Correct	93 ms	4516 KB	Output is correct
18	Correct	91 ms	4372 KB	Output is correct
19	Correct	85 ms	4508 KB	Output is correct
20	Correct	78 ms	4544 KB	Output is correct
21	Correct	68 ms	4500 KB	Output is correct
22	Execution timed out	1080 ms	4760 KB	Time limit exceeded
23	Halted	0 ms	0 KB	-