oj.uz

Submission #1116497

# Submission time Handle Problem Language Result Execution time Memory
1116497 2024-11-21T17:46:43 Z xnqs Nautilus (BOI19_nautilus) C++17
66 / 100
 25 ms 10832 KB 
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <cstring>

int x, y, p;
std::vector<std::string> arr;
std::string moves;
int dp[105][105][105];

const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};

inline bool in_mat(int i, int j) {
	return !(i<0||i>=x||j<0||j>=y);
}

int sol(int i, int j, int pos) {
	if (!in_mat(i,j)) {
		return 0;
	}
	if (arr[i][j]=='#') {
		return 0;
	}
	if (pos<0) {
		return 1;
	}
	if (dp[i][j][pos]!=-1) {
		return dp[i][j][pos];
	}

	int ret = 0;
	switch (moves[pos]) {
	case 'N':
		ret |= sol(i+1,j,pos-1);
		break;
	case 'S':
		ret |= sol(i-1,j,pos-1);
		break;
	case 'E':
		ret |= sol(i,j-1,pos-1);
		break;
	case 'W':
		ret |= sol(i,j+1,pos-1);
		break;
	default:
		for (int k = 0; k < 4; k++) {
			int iv = i+dx[k];
			int jv = j+dy[k];
			ret |= sol(iv,jv,pos-1);
		}
		break;
	}

	return dp[i][j][pos] = ret;
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cin >> x >> y >> p;
	arr.resize(x);
	for (auto& i : arr) {
		std::cin >> i;
	}
	std::cin >> moves;

	memset(dp,-1,sizeof(dp));
	int ret = 0;
	for (int i = 0; i < x; i++) {
		for (int j = 0; j < y; j++) {
			ret += sol(i,j,p-1);
		}
	}

	std::cout << ret << "\n";
}

Subtask #1
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4944 KB Output is correct
2 Correct 3 ms 4836 KB Output is correct
3 Correct 2 ms 4944 KB Output is correct
4 Correct 2 ms 4944 KB Output is correct
5 Correct 2 ms 4944 KB Output is correct
6 Correct 1 ms 4944 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4944 KB Output is correct
2 Correct 3 ms 4836 KB Output is correct
3 Correct 2 ms 4944 KB Output is correct
4 Correct 2 ms 4944 KB Output is correct
5 Correct 2 ms 4944 KB Output is correct
6 Correct 1 ms 4944 KB Output is correct
7 Correct 16 ms 4944 KB Output is correct
8 Correct 6 ms 4944 KB Output is correct
9 Correct 2 ms 4944 KB Output is correct
10 Correct 2 ms 5028 KB Output is correct
11 Correct 2 ms 4944 KB Output is correct
12 Correct 21 ms 4828 KB Output is correct
13 Correct 22 ms 4944 KB Output is correct
14 Correct 16 ms 4944 KB Output is correct
15 Correct 2 ms 4944 KB Output is correct
16 Correct 2 ms 4944 KB Output is correct
17 Correct 25 ms 4944 KB Output is correct
18 Correct 24 ms 4944 KB Output is correct
19 Correct 9 ms 4944 KB Output is correct
20 Correct 4 ms 5024 KB Output is correct
21 Correct 2 ms 4944 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4944 KB Output is correct
2 Correct 3 ms 4836 KB Output is correct
3 Correct 2 ms 4944 KB Output is correct
4 Correct 2 ms 4944 KB Output is correct
5 Correct 2 ms 4944 KB Output is correct
6 Correct 1 ms 4944 KB Output is correct
7 Correct 16 ms 4944 KB Output is correct
8 Correct 6 ms 4944 KB Output is correct
9 Correct 2 ms 4944 KB Output is correct
10 Correct 2 ms 5028 KB Output is correct
11 Correct 2 ms 4944 KB Output is correct
12 Correct 21 ms 4828 KB Output is correct
13 Correct 22 ms 4944 KB Output is correct
14 Correct 16 ms 4944 KB Output is correct
15 Correct 2 ms 4944 KB Output is correct
16 Correct 2 ms 4944 KB Output is correct
17 Correct 25 ms 4944 KB Output is correct
18 Correct 24 ms 4944 KB Output is correct
19 Correct 9 ms 4944 KB Output is correct
20 Correct 4 ms 5024 KB Output is correct
21 Correct 2 ms 4944 KB Output is correct
22 Runtime error 9 ms 10832 KB Execution killed with signal 11
23 Halted 0 ms 0 KB -