Submission #362730

#TimeUsernameProblemLanguageResultExecution timeMemory
362730knightron0Nautilus (BOI19_nautilus)C++14
100 / 100
311 ms159340 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define fr first #define sc second #define clr(a, x) memset(a, x, sizeof(a)) #define dbg(x) cout<<"("<<#x<<"): "<<x<<endl; #define printvector(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout<<*it<<" "; cout<<endl; #define all(v) v.begin(), v.end() #define lcm(a, b) (a * b)/__gcd(a, b) #define int long long int #define printvecpairs(vec) for(auto it: vec) cout<<it.fr<<' '<<it.sc<<endl; #define endl '\n' #define float long double const int MOD = 1e9 + 7; const int INF = 2e15; const int MAXN = 1e5 + 5; signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); #ifdef LOCAL freopen("input.txt", "r", stdin); #endif int n, m, k; cin>>n>>m>>k; char a[n][m]; bitset<502> grid[n]; for(int i= 0;i<n;i++){ bitset<502> b(0); for(int j= 0;j<m;j++){ cin>>a[i][j]; if(a[i][j] == '.') b[j] = 1; } grid[i] = b; } string s; cin>>s; bitset<502> dp[n+5][k+5]; for(int i= 0;i<n;i++){ dp[i][0] = grid[i]; } for(int i = 1;i<=k;i++){ for(int j= 0;j<n;j++){ if(s[i-1] == 'N' || s[i-1] == '?'){ if(j != n-1) dp[j][i] |= dp[j+1][i-1] & grid[j]; } if(s[i-1] == 'E' || s[i-1] == '?'){ dp[j][i] |= (dp[j][i-1] << 1) & grid[j]; } if(s[i-1] == 'W' || s[i-1] == '?'){ dp[j][i] |= (dp[j][i-1] >> 1) & grid[j]; } if(s[i-1] == 'S' || s[i-1] == '?'){ if(j > 0) dp[j][i] |= dp[j-1][i-1] & grid[j]; } } } int ans = 0; for(int j= 0;j<n;j++){ ans += dp[j][k].count(); } cout<<ans<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...