Submission #1201171

#TimeUsernameProblemLanguageResultExecution timeMemory
1201171browntoadNautilus (BOI19_nautilus)C++20
100 / 100
177 ms992 KiB
#include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; template<typename T> using pbds_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define ll long long #define int ll #define FOR(i, a, b) for (int i = (a); i < (b); i++) #define REP(i, n) FOR(i, 0, n) #define RREP(i, n) for (int i = (n)-1; i >= 0; i--) #define RREP1(i, n) for (int i = (n); i >= 1; i--) #define REP1(i, n) FOR(i, 1, n+1) #define pii pair<int, int> #define ppi pair<pii, int> #define pip pair<int, pii> #define f first #define s second #define pb push_back #define ALL(x) (x).begin(), (x).end() #define SZ(x) (int)((x).size()) #define endl '\n' #define IOS() ios::sync_with_stdio(false), cin.tie(0), cout.tie(0) const ll maxn = 505; const ll mod = 998244353; const ll inf = (1ll<<60); const int iinf = 1e9+5; ll pw(ll x, ll p, ll m){ ll ret = 1; x %= m; while(p > 0){ if (p & 1){ ret *= x; ret %= m; } x *= x; x %= m; p >>= 1; } return ret; } ll inv(ll x, ll m){ return pw(x, m-2, m); } bitset<maxn> dp[2][maxn]; // by row bitset<maxn> death[maxn]; int n, m, k; char arr[maxn][maxn]; vector<int> dx = {1, 0, -1, 0}; vector<int> dy = {0, 1, 0, -1}; vector<char> can = {'N', 'W', 'S', 'E'}; signed main(){ IOS(); cin>>n>>m>>k; REP1(i, n){ REP1(j, m){ cin>>arr[i][j]; if (arr[i][j] == '.') { dp[0][i][j] = 1; death[i][j] = 1; } } } string toad; cin>>toad; REP1(t, k){ bool b = (t&1); bool ob = (b^1); REP1(i, n) dp[b][i] = 0; if (toad[t-1] == 'N' || toad[t-1] == '?'){ REP1(i, n-1){ dp[b][i] |= dp[ob][i+1]; } } if (toad[t-1] == 'S' || toad[t-1] == '?'){ FOR(i, 2, n+1){ dp[b][i] |= dp[ob][i-1]; } } if (toad[t-1] == 'W' || toad[t-1] == '?'){ REP1(i, n) dp[b][i] |= (dp[ob][i]>>1); } if (toad[t-1] == 'E' || toad[t-1] == '?'){ REP1(i, n) dp[b][i] |= (dp[ob][i]<<1); } REP1(i, n) dp[b][i] &= death[i]; } int sm = 0; REP1(i, n){ REP1(j, m){ sm += dp[k&1][i][j]; } } cout<<sm<<endl; } /* 5 9 1 ...##.... ..#.##..# ..#....## .##...#.. ....#.... ? */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...