oj.uz

Submission #651011

# Submission time Handle Problem Language Result Execution time Memory
651011 2022-10-16T12:32:50 Z dooompy Nautilus (BOI19_nautilus) C++17
100 / 100
 302 ms 157412 KB 
#include "bits/stdc++.h"

using namespace std;

void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}



using ll = long long;

bitset<505> dp[505][5005], water[505];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("", "r", stdin);
//    freopen("", "w", stdout);
    int r, c, m; cin >> r >> c >> m;

    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            char cur; cin >> cur;

            if (cur == '.') {
                water[i].set(j, 1);
                dp[i][0].set(j, 1);
            }
        }
    }

    string command; cin >> command;

    for (int i = 1; i <= m; i++) {
        for (int row = 1; row <= r; row++) {
            switch (command[i -1]) {
                case 'N':
                    dp[row][i] = dp[row + 1][i-1] & water[row];
                    break;
                case 'E':
                    dp[row][i] = (dp[row][i-1] << 1) & water[row];
                    break;
                case 'S':
                    dp[row][i] = dp[row - 1][i-1] & water[row];
                    break;
                case 'W':
                    dp[row][i] = (dp[row][i-1] >> 1) & water[row];
                    break;
                case '?':
                    dp[row][i] = (dp[row + 1][i - 1] | (dp[row][i - 1] << 1) | dp[row - 1][i - 1] | (dp[row][i - 1] >> 1)) & water[row];
                    break;
            }
        }
    }

    int ans = 0;

    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            if (dp[i][m].test(j)) ans++;
        }
    }

    cout << ans;
}

Subtask #1
29.0 / 29.0

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

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Correct 2 ms 1364 KB Output is correct
3 Correct 1 ms 1364 KB Output is correct
4 Correct 1 ms 1364 KB Output is correct
5 Correct 1 ms 1364 KB Output is correct
6 Correct 1 ms 1364 KB Output is correct
7 Correct 1 ms 1364 KB Output is correct
8 Correct 1 ms 1364 KB Output is correct
9 Correct 2 ms 1364 KB Output is correct
10 Correct 2 ms 1364 KB Output is correct
11 Correct 2 ms 1364 KB Output is correct
12 Correct 2 ms 1364 KB Output is correct
13 Correct 2 ms 1364 KB Output is correct
14 Correct 3 ms 1492 KB Output is correct
15 Correct 2 ms 1416 KB Output is correct
16 Correct 2 ms 1364 KB Output is correct
17 Correct 2 ms 1364 KB Output is correct
18 Correct 2 ms 1364 KB Output is correct
19 Correct 2 ms 1364 KB Output is correct
20 Correct 2 ms 1364 KB Output is correct
21 Correct 3 ms 1364 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Correct 2 ms 1364 KB Output is correct
3 Correct 1 ms 1364 KB Output is correct
4 Correct 1 ms 1364 KB Output is correct
5 Correct 1 ms 1364 KB Output is correct
6 Correct 1 ms 1364 KB Output is correct
7 Correct 1 ms 1364 KB Output is correct
8 Correct 1 ms 1364 KB Output is correct
9 Correct 2 ms 1364 KB Output is correct
10 Correct 2 ms 1364 KB Output is correct
11 Correct 2 ms 1364 KB Output is correct
12 Correct 2 ms 1364 KB Output is correct
13 Correct 2 ms 1364 KB Output is correct
14 Correct 3 ms 1492 KB Output is correct
15 Correct 2 ms 1416 KB Output is correct
16 Correct 2 ms 1364 KB Output is correct
17 Correct 2 ms 1364 KB Output is correct
18 Correct 2 ms 1364 KB Output is correct
19 Correct 2 ms 1364 KB Output is correct
20 Correct 2 ms 1364 KB Output is correct
21 Correct 3 ms 1364 KB Output is correct
22 Correct 165 ms 157064 KB Output is correct
23 Correct 170 ms 157324 KB Output is correct
24 Correct 187 ms 157260 KB Output is correct
25 Correct 162 ms 157232 KB Output is correct
26 Correct 143 ms 157240 KB Output is correct
27 Correct 223 ms 157260 KB Output is correct
28 Correct 254 ms 157308 KB Output is correct
29 Correct 222 ms 157320 KB Output is correct
30 Correct 225 ms 157268 KB Output is correct
31 Correct 214 ms 157276 KB Output is correct
32 Correct 256 ms 157292 KB Output is correct
33 Correct 265 ms 157320 KB Output is correct
34 Correct 266 ms 157328 KB Output is correct
35 Correct 273 ms 157412 KB Output is correct
36 Correct 302 ms 157256 KB Output is correct