Submission #900602

#TimeUsernameProblemLanguageResultExecution timeMemory
900602mraronNautilus (BOI19_nautilus)C++14
100 / 100
165 ms157520 KiB
#include<iostream> #include<vector> #include<map> #include<set> #include<cassert> #include<unordered_map> #include<unordered_set> #include<functional> #include<queue> #include<stack> #include<cstring> #include<algorithm> #include<cmath> #include<sstream> #include<iomanip> #include<cstdio> #include<cstdlib> #include<numeric> #include<random> #include<chrono> #include<bitset> //#include<ext/pb_ds/assoc_container.hpp> //#include<ext/pb_ds/tree_policy.hpp> using namespace std; //using namespace __gnu_pbds; #define all(x) (x).begin(), (x).end() #define pb push_back #define eb emplace_back #define xx first #define yy second #define sz(x) (int)(x).size() #define gc getchar #define IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define mp make_pair #define ins insert #ifndef ONLINE_JUDGE # define LOG(x) (cerr << #x << " = " << (x) << endl) #else # define LOG(x) ((void)0) #endif using ll = long long; using ull = unsigned long long ; using ld = long double ; using str = string; //using ordered_set=tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update>; const double PI=acos(-1); const ll INF = 1LL<<62; const ll MINF = -(1LL<<62); template<typename T> T getint() { T val=0; char c; bool neg=false; while((c=gc()) && !(c>='0' && c<='9')) { neg|=c=='-'; } do { val=(val*10)+c-'0'; } while((c=gc()) && (c>='0' && c<='9')); return val*(neg?-1:1); } //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); uniform_int_distribution<int>(0, n-1)(rng) int n,m,k; string t[501]; bitset<501> dp[501][5001]; int main() { IO; cin>>n>>m>>k; for(int i=0;i<n;++i) cin>>t[i]; for(int i=0;i<n;++i) { for(int j=0;j<m;++j) { if(t[i][j]=='.') dp[i][0][j]=1; } } string s; cin>>s; for(int i=1;i<=sz(s);++i) { bool q=s[i-1]=='?'; if(q||s[i-1]=='S') for(int r=1;r<n;++r) { dp[r][i]|=dp[r-1][i-1]; } if(q||s[i-1]=='N') for(int r=0;r+1<n;++r) { dp[r][i]|=dp[r+1][i-1]; } if(q||s[i-1]=='W') for(int r=0;r<n;++r) { dp[r][i]|=dp[r][i-1]>>1; } if(q||s[i-1]=='E') for(int r=0;r<n;++r) { dp[r][i]|=dp[r][i-1]<<1; } for(int r=0;r<n;++r) { dp[r][i]&=dp[r][0]; } //~ for(int r=0;r<n;++r){ //~ for(int j=0;j<m;++j) { //~ cerr<<dp[r][i][j]<<" "; //~ }cerr<<"\n"; //~ } } int ans=0; for(int i=0;i<n;++i) { ans+=dp[i][sz(s)].count(); } cout<<ans<<"\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...