oj.uz

Submission #645083

# Submission time Handle Problem Language Result Execution time Memory
645083 2022-09-26T07:30:55 Z mychecksedad Nautilus (BOI19_nautilus) C++17
66 / 100
 49 ms 67016 KB 
/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define PI 3.1415926535
#define pb push_back
#define setp() cout << setprecision(15)
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " is " << x << '\n';
const int N = 1e6+100, M = 1e5+10, F = 2147483646, K = 20;



int n, m, k, arr[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
bool dp[105][105][105];
string s[N], t;
void solve(){
    cin >> n >> m >> k;
    for(int i = 0; i < n; ++i) cin >> s[i];
    cin >> t;
    for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j) for(int l = 0; l <= k; ++l) dp[i][j][l] = 0;
    for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j) if(s[i][j] == '.') dp[i][j][0] = 1;
    int ans = 0;
    for(int l = 1; l <= k; ++l){
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < m; ++j){
                if(dp[i][j][l - 1]){
                    int x = i, y = j;
                    if(t[l - 1] == '?'){
                        for(int h = 0; h < 4; ++h){
                            x += arr[h][0], y += arr[h][1];
                            if(x>=0&&x<n&&y>=0&&y<m&&s[x][y]=='.') dp[x][y][l] = 1;
                            x -= arr[h][0], y -= arr[h][1];
                        }
                    }else{
                        if(t[l - 1] == 'N') x--;
                        else if(t[l - 1] == 'S') x++;
                        else if(t[l - 1] == 'W') y--;
                        else y++;
                        if(x>=0&&x<n&&y>=0&&y<m&&s[x][y]=='.') dp[x][y][l] = 1;
                    }
                }
            }
        }
    }
    for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j) ans += dp[i][j][k];
    cout << ans;
}





int main(){
    cin.tie(0); ios::sync_with_stdio(0);
    int T = 1, aa;
    // cin >> T;aa=T;
    while(T--){
        // cout << "Case #" << aa-T << ": ";
        solve();
        cout << '\n';
    }
    return 0;
 
}

Compilation message

nautilus.cpp: In function 'int main()':
nautilus.cpp:59:16: warning: unused variable 'aa' [-Wunused-variable]
   59 |     int T = 1, aa;
      |                ^~

Subtask #1
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 32740 KB Output is correct
2 Correct 17 ms 32632 KB Output is correct
3 Correct 18 ms 32652 KB Output is correct
4 Correct 17 ms 32724 KB Output is correct
5 Correct 18 ms 32740 KB Output is correct
6 Correct 22 ms 32724 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 32740 KB Output is correct
2 Correct 17 ms 32632 KB Output is correct
3 Correct 18 ms 32652 KB Output is correct
4 Correct 17 ms 32724 KB Output is correct
5 Correct 18 ms 32740 KB Output is correct
6 Correct 22 ms 32724 KB Output is correct
7 Correct 29 ms 32672 KB Output is correct
8 Correct 20 ms 32664 KB Output is correct
9 Correct 19 ms 32724 KB Output is correct
10 Correct 18 ms 32724 KB Output is correct
11 Correct 18 ms 32716 KB Output is correct
12 Correct 36 ms 32644 KB Output is correct
13 Correct 38 ms 32668 KB Output is correct
14 Correct 30 ms 32724 KB Output is correct
15 Correct 18 ms 32736 KB Output is correct
16 Correct 17 ms 32680 KB Output is correct
17 Correct 43 ms 32724 KB Output is correct
18 Correct 39 ms 32728 KB Output is correct
19 Correct 28 ms 32732 KB Output is correct
20 Correct 21 ms 32656 KB Output is correct
21 Correct 18 ms 32724 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 32740 KB Output is correct
2 Correct 17 ms 32632 KB Output is correct
3 Correct 18 ms 32652 KB Output is correct
4 Correct 17 ms 32724 KB Output is correct
5 Correct 18 ms 32740 KB Output is correct
6 Correct 22 ms 32724 KB Output is correct
7 Correct 29 ms 32672 KB Output is correct
8 Correct 20 ms 32664 KB Output is correct
9 Correct 19 ms 32724 KB Output is correct
10 Correct 18 ms 32724 KB Output is correct
11 Correct 18 ms 32716 KB Output is correct
12 Correct 36 ms 32644 KB Output is correct
13 Correct 38 ms 32668 KB Output is correct
14 Correct 30 ms 32724 KB Output is correct
15 Correct 18 ms 32736 KB Output is correct
16 Correct 17 ms 32680 KB Output is correct
17 Correct 43 ms 32724 KB Output is correct
18 Correct 39 ms 32728 KB Output is correct
19 Correct 28 ms 32732 KB Output is correct
20 Correct 21 ms 32656 KB Output is correct
21 Correct 18 ms 32724 KB Output is correct
22 Runtime error 49 ms 67016 KB Execution killed with signal 11
23 Halted 0 ms 0 KB -