oj.uz

Submission #828608

# Submission time Handle Problem Language Result Execution time Memory
828608 2023-08-17T12:43:20 Z arashMLG Nautilus (BOI19_nautilus) C++17
100 / 100
 134 ms 896 KB 
#include<bits/stdc++.h>
#ifdef LOCAL
#include "Essentials/algo/debug.h"
#else
#define debug(...) 69
#endif
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

//https://quera.org/profile/4dykhk

typedef long long     ll;
typedef long double   ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll>   pll;

const int N = 500 + 23;
const ll mod = 1e9+7; // 998244353
const int LOG = 23;
const ll inf = 1e18;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define F           first
#define S           second
#define pb          push_back
#define ms(x,y)     memset((x) , (y) , sizeof (x))
#define done        return cout<<endl , 0;
#define kill(x)     cout<<x<<endl, exit(0);
#define isIn(x,s,e) ((x) >= (s) && (x) <= e)
#define all(x)      x.begin(),x.end()
#define sz(x)       (int)x.size()
#define pc(x)       __builtin_popcount(x)
#define ctz(x)      __builtin_ctz(x)
#define MinHeap(x)  priority_queue<x, vector<x> , greater<x> >
#define MaxHeap(x)  priority_queue<x, vector<x>>
#define lc          (v << 1)
#define rc          ((v<<1) |1)
#define int         ll

ll pw(ll a, ll b, ll md = mod){ll res = 1; while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}


int n,m,k;
bitset<N*N> ok,dp;

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(false);
   	cin>>n>>m>>k;
   	for(int i = 0 ; i < n ; i++) {
		for(int j = 0 ;j < m;j ++) {
			char c; cin>>c; 
			ok[i*N + j] = c == '.';
		}
	}
	dp = ok;
	for(int i = 0 ;i < k; i ++) {
		char c; cin>>c;
		if(c == 'E') dp = (dp << 1);
		if(c == 'W') dp = (dp >> 1);
		if(c == 'N') dp = (dp >> N);
		if(c == 'S') dp = (dp << N);
		if(c == '?') dp = ((dp << 1) | (dp >> 1) | (dp >> N) | (dp << N));
		dp = dp & ok;
	}
	cout<<dp.count();
	done;
}

Subtask #1
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 1 ms 572 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 2 ms 732 KB Output is correct
5 Correct 1 ms 568 KB Output is correct
6 Correct 1 ms 596 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 1 ms 572 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 2 ms 732 KB Output is correct
5 Correct 1 ms 568 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 2 ms 652 KB Output is correct
8 Correct 3 ms 724 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 4 ms 596 KB Output is correct
13 Correct 3 ms 596 KB Output is correct
14 Correct 3 ms 596 KB Output is correct
15 Correct 4 ms 608 KB Output is correct
16 Correct 3 ms 564 KB Output is correct
17 Correct 3 ms 568 KB Output is correct
18 Correct 3 ms 596 KB Output is correct
19 Correct 3 ms 596 KB Output is correct
20 Correct 3 ms 596 KB Output is correct
21 Correct 3 ms 596 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 1 ms 572 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 2 ms 732 KB Output is correct
5 Correct 1 ms 568 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 2 ms 652 KB Output is correct
8 Correct 3 ms 724 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 4 ms 596 KB Output is correct
13 Correct 3 ms 596 KB Output is correct
14 Correct 3 ms 596 KB Output is correct
15 Correct 4 ms 608 KB Output is correct
16 Correct 3 ms 564 KB Output is correct
17 Correct 3 ms 568 KB Output is correct
18 Correct 3 ms 596 KB Output is correct
19 Correct 3 ms 596 KB Output is correct
20 Correct 3 ms 596 KB Output is correct
21 Correct 3 ms 596 KB Output is correct
22 Correct 63 ms 892 KB Output is correct
23 Correct 66 ms 888 KB Output is correct
24 Correct 79 ms 852 KB Output is correct
25 Correct 63 ms 852 KB Output is correct
26 Correct 61 ms 888 KB Output is correct
27 Correct 119 ms 892 KB Output is correct
28 Correct 103 ms 892 KB Output is correct
29 Correct 103 ms 892 KB Output is correct
30 Correct 103 ms 896 KB Output is correct
31 Correct 103 ms 852 KB Output is correct
32 Correct 131 ms 888 KB Output is correct
33 Correct 131 ms 832 KB Output is correct
34 Correct 131 ms 884 KB Output is correct
35 Correct 131 ms 892 KB Output is correct
36 Correct 134 ms 852 KB Output is correct