oj.uz

Submission #593722

# Submission time Handle Problem Language Result Execution time Memory
593722 2022-07-11T14:04:18 Z nguyentu Nautilus (BOI19_nautilus) C++14
66 / 100
 860 ms 4952 KB 
#include <bits/stdc++.h>

#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;

#define ii pair<int , int>  
#define iv pair<ii , ii>
#define iii pair<int , ii>
#define fi first
#define se second
//#define int long long
const int inf = 1e9 + 7;
const int MAX_N = 5e2 + 7;
const int MOD = 1e9 + 7;

char a[MAX_N][MAX_N];
int f[MAX_N][MAX_N][107];
char s[5007];
bitset<5007> dp[2][MAX_N];
bitset<5007> d[MAX_N];

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    int n , m , l; cin >> n >> m >> l;
    //subtask 1&2
    if (n <= 100 && m <= 100 && l <= 100) {
        for (int i = 1 ; i <= n ; i++) {
            for (int j = 1 ; j <= m ; j++) {
                cin >> a[i][j];
            }
        }   
        
        for (int i = 1 ; i <= l ; i++) {
            cin >> s[i];
        }
        for (int i = 1 ; i <= n ; i++) {
            for (int j = 1 ; j <= m ; j++) {
                if (a[i][j] != '#') {
                    f[i][j][0] = 1;
                } 
            }
        }
        for (int h = 1 ; h <= l ; h++) {
            for (int i = 1 ; i <= n ;i ++) {
                for (int j = 1 ; j <= m ; j++) {
                    if (a[i][j] == '#') continue;;
                    if (s[h] == 'W' && j < m) {
                        f[i][j][h] = f[i][j + 1][h - 1];
                    }
                    if (s[h] == 'N' && i < n) {
                        f[i][j][h] = f[i + 1][j][h - 1]; 
                    }
                    if (s[h] == 'E' && 1 < j) {
                        f[i][j][h] = f[i][j - 1][h - 1];
                    }
                    if (s[h] == 'S' && 1 < i) {
                        f[i][j][h] = f[i - 1][j][h - 1];
                    }
                    if (s[h] == '?') {
                        if (j < m && f[i][j + 1][h - 1]) f[i][j][h] = f[i][j + 1][h - 1];
                        if (i < n && f[i + 1][j][h - 1]) f[i][j][h] = f[i + 1][j][h - 1];
                        if (1 < j && f[i][j - 1][h - 1]) f[i][j][h] = f[i][j - 1][h - 1];
                        if (1 < i && f[i - 1][j][h - 1]) f[i][j][h] = f[i - 1][j][h - 1];
                    }
                }
            }
        }
        int ans = 0;

        for (int i = 1 ; i <= n ;i ++) {
            for (int j = 1 ; j <= m ; j++) {
            if (f[i][j][l]) {
                    ans++;
                }
                //cout << f[i][j][l] << " ";
            }
            //cout << '\n';
        }
        cout << ans;
    }
    else {
    //subtask 3
        for (int i = 0 ; i < n ; i++) {
            d[i].flip();
            dp[1][i].flip();
            for (int j = 0 ; j < m ; j++) {
                cin >> a[i][j];
                if (a[i][j] == '#') {
                    d[i][j].flip();
                    dp[1][i][j].flip();
                }
            }
        }
        for (int i = 0 ; i < l ; i++) {
            cin >> s[i];
        }
        for (int i = 0 ; i < l ; i++) {
            int now = i & 1;
            int prev = now ^ 1;
            for (int j = 0 ; j < n ; j++) {
                if (s[i] == 'W') {
                    dp[now][j] = dp[prev][j] << 1;
                }
                else if (s[i] == 'E') {
                    dp[now][j] = dp[prev][j] >> 1;
                }
                else if (s[i] == 'S') {
                    dp[now][j] = dp[prev][j - 1];
                }
                else if (s[i] == 'N') {
                    dp[now][j] = dp[prev][j + 1];
                }
                else if (s[i] == '?') {
                    dp[now][j] |= dp[prev][j - 1];
                    dp[now][j] |= dp[prev][j + 1];
                    dp[now][j] |= (dp[prev][j] >> 1);
                    dp[now][j] |= (dp[prev][j] << 1);
                }
            }
            for (int j = 0 ; j < n ; j++) {
                dp[now][j] = dp[now][j] & d[j];
                dp[prev][j] = dp[now][j];
            }
        }
        int ans = 0;
        // for (int i = 0 ; i < n ; i++) {
        //     for (int j = 0 ; j < m ; j++) {
        //         if (f[(l - 1) & 1][i][j]) {
        //             ans++;
        //         }
        //     }
        // }
        cout << ans;
    }
    return 0;
}

Subtask #1
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 5 ms 4932 KB Output is correct
3 Correct 6 ms 4820 KB Output is correct
4 Correct 7 ms 4820 KB Output is correct
5 Correct 4 ms 4308 KB Output is correct
6 Correct 2 ms 468 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 5 ms 4932 KB Output is correct
3 Correct 6 ms 4820 KB Output is correct
4 Correct 7 ms 4820 KB Output is correct
5 Correct 4 ms 4308 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 7 ms 4868 KB Output is correct
8 Correct 9 ms 4912 KB Output is correct
9 Correct 9 ms 4820 KB Output is correct
10 Correct 5 ms 4308 KB Output is correct
11 Correct 2 ms 416 KB Output is correct
12 Correct 8 ms 4952 KB Output is correct
13 Correct 11 ms 4928 KB Output is correct
14 Correct 13 ms 4820 KB Output is correct
15 Correct 7 ms 4368 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 6 ms 4948 KB Output is correct
18 Correct 11 ms 4924 KB Output is correct
19 Correct 11 ms 4828 KB Output is correct
20 Correct 8 ms 4308 KB Output is correct
21 Correct 3 ms 452 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 5 ms 4932 KB Output is correct
3 Correct 6 ms 4820 KB Output is correct
4 Correct 7 ms 4820 KB Output is correct
5 Correct 4 ms 4308 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 7 ms 4868 KB Output is correct
8 Correct 9 ms 4912 KB Output is correct
9 Correct 9 ms 4820 KB Output is correct
10 Correct 5 ms 4308 KB Output is correct
11 Correct 2 ms 416 KB Output is correct
12 Correct 8 ms 4952 KB Output is correct
13 Correct 11 ms 4928 KB Output is correct
14 Correct 13 ms 4820 KB Output is correct
15 Correct 7 ms 4368 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 6 ms 4948 KB Output is correct
18 Correct 11 ms 4924 KB Output is correct
19 Correct 11 ms 4828 KB Output is correct
20 Correct 8 ms 4308 KB Output is correct
21 Correct 3 ms 452 KB Output is correct
22 Incorrect 860 ms 1500 KB Output isn't correct
23 Halted 0 ms 0 KB -