oj.uz

Submission #221342

# Submission time Handle Problem Language Result Execution time Memory
221342 2020-04-09T22:06:55 Z Leonardo_Paes Nautilus (BOI19_nautilus) C++17
66 / 100
 46 ms 12412 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 110;

int r, c, m, ans;

int dp[maxn][maxn][maxn], mat[maxn][maxn], mark[maxn][maxn];

int ih[] = {-1, +1, 0, 0};
int jh[] = {0, 0, +1, -1};

string s;

map<char, int> mp;

int solve(int i, int j, int pos){
    if(pos == (int)s.size()) return mark[i][j] = 1;
    if(dp[i][j][pos] != -1) return dp[i][j][pos];

    int tot = 0;

    if(s[pos] == '?'){
        for(int k=0; k<4; k++){
            int newi = i + ih[k], newj = j + jh[k];

            if(newi >= 1 and newi <= r and newj >= 1 and newj <= c and mat[newi][newj]){
                tot |= solve(newi, newj, pos+1);
            }
        }
    }
    else{
        int newi = i + ih[mp[s[pos]]], newj = j + jh[mp[s[pos]]];

        if(newi >= 1 and newi <= r and newj >= 1 and newj <= c and mat[newi][newj]){
            tot |= solve(newi, newj, pos+1);
        }
    }

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

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

    cin >> r >> c >> m;

    for(int i=1; i<=r; i++){
        for(int j=1; j<=c; j++){
            char a;

            cin >> a;

            if(a == '.') mat[i][j] = 1;
        }
    }

    cin >> s;

    mp['N'] = 0;
    mp['S'] = 1;
    mp['E'] = 2;
    mp['W'] = 3;

    memset(dp, -1, sizeof dp);

    int ans = 0;

    for(int i=1; i<=r; i++){
        for(int j=1; j<=c; j++){
            if(mat[i][j]) solve(i, j, 0);
        }
    }

    for(int i=1; i<=r; i++){
        for(int j=1; j<=c; j++){
            ans += mark[i][j];
        }
    }

    cout << ans << "\n";

    return 0;
}

Subtask #1
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 5632 KB Output is correct
2 Correct 8 ms 5632 KB Output is correct
3 Correct 8 ms 5632 KB Output is correct
4 Correct 8 ms 5632 KB Output is correct
5 Correct 7 ms 5632 KB Output is correct
6 Correct 7 ms 5632 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 5632 KB Output is correct
2 Correct 8 ms 5632 KB Output is correct
3 Correct 8 ms 5632 KB Output is correct
4 Correct 8 ms 5632 KB Output is correct
5 Correct 7 ms 5632 KB Output is correct
6 Correct 7 ms 5632 KB Output is correct
7 Correct 40 ms 5760 KB Output is correct
8 Correct 14 ms 5632 KB Output is correct
9 Correct 9 ms 5632 KB Output is correct
10 Correct 8 ms 5632 KB Output is correct
11 Correct 9 ms 5632 KB Output is correct
12 Correct 43 ms 5632 KB Output is correct
13 Correct 41 ms 5632 KB Output is correct
14 Correct 30 ms 5760 KB Output is correct
15 Correct 8 ms 5632 KB Output is correct
16 Correct 7 ms 5632 KB Output is correct
17 Correct 44 ms 5632 KB Output is correct
18 Correct 46 ms 5632 KB Output is correct
19 Correct 22 ms 5632 KB Output is correct
20 Correct 10 ms 5692 KB Output is correct
21 Correct 7 ms 5632 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 5632 KB Output is correct
2 Correct 8 ms 5632 KB Output is correct
3 Correct 8 ms 5632 KB Output is correct
4 Correct 8 ms 5632 KB Output is correct
5 Correct 7 ms 5632 KB Output is correct
6 Correct 7 ms 5632 KB Output is correct
7 Correct 40 ms 5760 KB Output is correct
8 Correct 14 ms 5632 KB Output is correct
9 Correct 9 ms 5632 KB Output is correct
10 Correct 8 ms 5632 KB Output is correct
11 Correct 9 ms 5632 KB Output is correct
12 Correct 43 ms 5632 KB Output is correct
13 Correct 41 ms 5632 KB Output is correct
14 Correct 30 ms 5760 KB Output is correct
15 Correct 8 ms 5632 KB Output is correct
16 Correct 7 ms 5632 KB Output is correct
17 Correct 44 ms 5632 KB Output is correct
18 Correct 46 ms 5632 KB Output is correct
19 Correct 22 ms 5632 KB Output is correct
20 Correct 10 ms 5692 KB Output is correct
21 Correct 7 ms 5632 KB Output is correct
22 Runtime error 38 ms 12412 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Halted 0 ms 0 KB -