oj.uz

Submission #496488

# Submission time Handle Problem Language Result Execution time Memory
496488 2021-12-21T10:53:08 Z ergagan Nautilus (BOI19_nautilus) C++17
100 / 100
 371 ms 178604 KB 
//я так много думал, что опять попал
#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define f first
#define s second
#define left(v) v + v
#define right(v) v + v + 1
#define ub upper_bound
#define lb lower_bound

using namespace std;
typedef long long ll;

//17 SEVENTEEN
const long double Pi = acos(-1.0);
const ll dx[] = {0,0,1,-1};
const ll dy[] = {1,-1,0,0};
const ll N = (ll) 1e6 + 17;
const ll M = (ll) 5e2 + 69;
const ll inf = (ll) 1e14 + 3;
const ll mod = (ll) 1e9 + 7;
ll sq(ll x) { return x * x; }

ll zxc = 1, n, m, sz, ans;

char c;
bitset<M> dp[M][M * 10];

void solve() {

    cin >> n >> m >> sz;

    for(ll i = 1; i <= n; i++) {
        for(ll j = 1; j <= m; j++) {
            cin >> c;
            if(c == '#') dp[i][0][j] = 0;
            else dp[i][0][j] = 1;
        }
    }

    for(ll k = 1; k <= sz; k++) {
        cin >> c;
        for(ll i = 1; i <= n; i++) {
            dp[i][k] = dp[i][0];
            if(c == 'N') dp[i][k] &= dp[i + 1][k - 1];
            if(c == 'S') dp[i][k] &= dp[i - 1][k - 1];
            if(c == 'W') dp[i][k] &= (dp[i][k - 1] >> 1);
            if(c == 'E') dp[i][k] &= (dp[i][k - 1] << 1);
            if(c == '?') dp[i][k] &= ((dp[i - 1][k - 1] | dp[i + 1][k - 1]) | ((dp[i][k - 1] << 1) | (dp[i][k - 1] >> 1)));
//            cout << dp[i][k] << " ";
        }
//        cout << "\n";
    }

    for(ll i = 1; i <= n; i++) {
        ans += dp[i][sz].count();
    }
    cout << ans;
}

/*

5 9 7
...##....
..#.##..#
..#....##
.##...#..
....#....
WSWEENN

*/

int main(/*Уверенно*/) {
ios_base::sync_with_stdio(0);
    cin.tie(0);
/*
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);
*/
//    cin >> zxc;
    while(zxc--) {
        solve();
    }
  	return 0;
}
// さよならさ いかなくちゃ

Subtask #1
29.0 / 29.0

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

Subtask #2
37.0 / 37.0

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

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1484 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct
4 Correct 1 ms 1484 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct
6 Correct 2 ms 1484 KB Output is correct
7 Correct 1 ms 1484 KB Output is correct
8 Correct 1 ms 1484 KB Output is correct
9 Correct 1 ms 1484 KB Output is correct
10 Correct 1 ms 1484 KB Output is correct
11 Correct 2 ms 1484 KB Output is correct
12 Correct 1 ms 1484 KB Output is correct
13 Correct 1 ms 1484 KB Output is correct
14 Correct 1 ms 1484 KB Output is correct
15 Correct 2 ms 1484 KB Output is correct
16 Correct 1 ms 1484 KB Output is correct
17 Correct 1 ms 1484 KB Output is correct
18 Correct 2 ms 1484 KB Output is correct
19 Correct 2 ms 1484 KB Output is correct
20 Correct 2 ms 1484 KB Output is correct
21 Correct 1 ms 1484 KB Output is correct
22 Correct 187 ms 178452 KB Output is correct
23 Correct 198 ms 178504 KB Output is correct
24 Correct 211 ms 178484 KB Output is correct
25 Correct 229 ms 178500 KB Output is correct
26 Correct 212 ms 178500 KB Output is correct
27 Correct 241 ms 178604 KB Output is correct
28 Correct 238 ms 178408 KB Output is correct
29 Correct 261 ms 178400 KB Output is correct
30 Correct 267 ms 178480 KB Output is correct
31 Correct 303 ms 178408 KB Output is correct
32 Correct 358 ms 178460 KB Output is correct
33 Correct 332 ms 178440 KB Output is correct
34 Correct 371 ms 178568 KB Output is correct
35 Correct 269 ms 178436 KB Output is correct
36 Correct 252 ms 178480 KB Output is correct