oj.uz

Submission #729801

# Submission time Handle Problem Language Result Execution time Memory
729801 2023-04-24T15:36:43 Z vjudge1 Nautilus (BOI19_nautilus) C++14
66 / 100
 50 ms 5324 KB 
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <stack>
#include <set>
using namespace std;
const int maxn = 105;
int n, m, sz;
char mat[maxn][maxn];
int dp[maxn][maxn][maxn];
string s;
int di[] = {-1, 1, 0, 0};
int dj[] = {0, 0, -1, 1};
set<pair<int, int> > st;
int rec(int i, int j, int at) {
    if(at == sz) {
        st.insert({i, j});
//        cout << "DA" << endl;
        return 1;
    }
    if(dp[i][j][at] != -1) {
        return dp[i][j][at];
    }
    int result = 0;
    if(s[at] == 'N') {
        if(i - 1 >= 0 and mat[i - 1][j] != '#') {
            result = max(result, rec(i - 1, j, at + 1));
        }
    }
    if(s[at] == 'S') {
        if(i + 1 < n and mat[i + 1][j] != '#') {
            result = max(result, rec(i + 1, j, at + 1));
        }
    }
    if(s[at] == 'W') {
        if(j - 1 >= 0 and mat[i][j - 1] != '#') {
            result = max(result, rec(i, j - 1, at + 1));
        }
    }
    if(s[at] == 'E') {
        if(j + 1 < m and mat[i][j + 1] != '#') {
            result = max(result, rec(i, j + 1, at + 1));
        }
    }
    if(s[at] == '?') {
        for(int k = 0; k < 4; k++) {
            int ti = i + di[k];
            int tj = j + dj[k];
            if(ti >= 0 and tj >= 0 and ti < n and tj < m and mat[ti][tj] != '#') {
                result = max(result, rec(ti, tj, at + 1));
            }
        }
    }
    return  dp[i][j][at] = result;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin >> n >> m >> sz;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> mat[i][j];
        }
    }
    cin >> s;
    int res = 0;
    memset(dp, -1, sizeof dp);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(mat[i][j] != '#') {
//                res++;
            }
            if(mat[i][j] != '#' and rec(i, j, 0) == 1) {
                
            }
        }
    }
    cout << st.size() << endl;
    return 0;
}
/*
 5 9 7
...##....
..#.##..#
..#....##
.##...#..
....#....
WS?EE??
 
 
 **/

Compilation message

nautilus.cpp: In function 'int main()':
nautilus.cpp:68:9: warning: unused variable 'res' [-Wunused-variable]
   68 |     int res = 0;
      |         ^~~

Subtask #1
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 5204 KB Output is correct
2 Correct 4 ms 4820 KB Output is correct
3 Correct 4 ms 4860 KB Output is correct
4 Correct 2 ms 4820 KB Output is correct
5 Correct 3 ms 4800 KB Output is correct
6 Correct 2 ms 4820 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 5204 KB Output is correct
2 Correct 4 ms 4820 KB Output is correct
3 Correct 4 ms 4860 KB Output is correct
4 Correct 2 ms 4820 KB Output is correct
5 Correct 3 ms 4800 KB Output is correct
6 Correct 2 ms 4820 KB Output is correct
7 Correct 31 ms 5292 KB Output is correct
8 Correct 9 ms 4820 KB Output is correct
9 Correct 4 ms 4820 KB Output is correct
10 Correct 3 ms 4820 KB Output is correct
11 Correct 3 ms 4816 KB Output is correct
12 Correct 38 ms 5316 KB Output is correct
13 Correct 38 ms 5196 KB Output is correct
14 Correct 24 ms 5104 KB Output is correct
15 Correct 3 ms 4820 KB Output is correct
16 Correct 3 ms 4812 KB Output is correct
17 Correct 48 ms 5324 KB Output is correct
18 Correct 50 ms 5156 KB Output is correct
19 Correct 13 ms 4948 KB Output is correct
20 Correct 7 ms 4820 KB Output is correct
21 Correct 3 ms 4820 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 5204 KB Output is correct
2 Correct 4 ms 4820 KB Output is correct
3 Correct 4 ms 4860 KB Output is correct
4 Correct 2 ms 4820 KB Output is correct
5 Correct 3 ms 4800 KB Output is correct
6 Correct 2 ms 4820 KB Output is correct
7 Correct 31 ms 5292 KB Output is correct
8 Correct 9 ms 4820 KB Output is correct
9 Correct 4 ms 4820 KB Output is correct
10 Correct 3 ms 4820 KB Output is correct
11 Correct 3 ms 4816 KB Output is correct
12 Correct 38 ms 5316 KB Output is correct
13 Correct 38 ms 5196 KB Output is correct
14 Correct 24 ms 5104 KB Output is correct
15 Correct 3 ms 4820 KB Output is correct
16 Correct 3 ms 4812 KB Output is correct
17 Correct 48 ms 5324 KB Output is correct
18 Correct 50 ms 5156 KB Output is correct
19 Correct 13 ms 4948 KB Output is correct
20 Correct 7 ms 4820 KB Output is correct
21 Correct 3 ms 4820 KB Output is correct
22 Runtime error 2 ms 724 KB Execution killed with signal 11
23 Halted 0 ms 0 KB -