Submission #221670

#	Time	Username	Problem	Language	Result	Execution time	Memory
221670		NaimSS	Nautilus (BOI19_nautilus)	C++14	100 / 100	197 ms	768 KiB

nautilus

#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define ff first
#define ss second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define endl "\n"
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb(x) push_back(x)
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef pair<ll,ll> pll;
typedef vector<string> vs;
typedef vector<pll> vpl;
typedef vector<int> vi;
inline int mod(int n, int m){ int ret = n%m; if(ret < 0) ret += m; return ret; }
ll gcd(ll a, ll b){return (b == 0 ? a : gcd(b, a%b));}
ll exp(ll a,ll b,ll m){
    if(b==0LL) return 1LL;
    if(b==1LL) return mod(a,m);
    ll k = mod(exp(a,b/2,m),m);
    if(b&1LL){
        return mod(a*mod(k*k,m),m);
    }
    else return mod(k*k,m);
 
}

const int N = 505;
const int M = 5050;
bitset<N> dp[N];
bitset<N> dp2[N];
bitset<N> mat[N];
char s[M];
int32_t main(){
  fastio;
  int r,c,m;
  cin>>r>>c>>m;
  for(int i=0;i<r;i++){
    for(int j=0;j<c;j++){
      char c;
      cin>>c;
      mat[i][j] = (c=='#'?0:1);
    }
  }
  for(int i=1;i<=m;i++){
    cin>>s[i];
    
  }
  for(int i=0;i<r;i++){
      dp[i] = mat[i];
  }
  for(int it=1;it<=m;it++){
    if(s[it]=='N'){
      for(int i=0;i<r;i++){
        if(i+1<r)dp[i] = (dp[i+1]&mat[i]);
        else dp[i].reset();
      }
    }else if(s[it]=='S'){
      
      for(int i=r-1;i>=0;i--){
        if(i-1>=0)dp[i] = (dp[i-1]&mat[i]);
        else dp[i].reset();
      }

    }else if(s[it]=='W'){
      for(int i=0;i<r;i++){
        dp[i] = ((dp[i]>>1)&mat[i]);
      }
    }else if(s[it]=='E'){
      //
      for(int i=0;i<r;i++){
        dp[i] = ((dp[i]<<1)&mat[i]);
      }

      //
    }else{

      for(int i=0;i<r;i++){
        dp2[i] = ((dp[i]>>1)&mat[i]);
      }
      for(int i=0;i<r;i++){
        dp2[i]|= ((dp[i]<<1)&mat[i]);
      }
      for(int i=0;i<r;i++){
        if(i+1<r)dp2[i]|=(dp[i+1]&mat[i]);
        if(i-1>=0)dp2[i]|=(dp[i-1]&mat[i]);
      }
      for(int i=0;i<r;i++)dp[i]=dp2[i];
    }



  }
  int tot=0;
  for(int i=0;i<r;i++){
    for(int j=0;j<c;j++){
      if(dp[i][j]==1)tot++;
    }
  }
  cout<<tot<<endl;

  // Math -> gcd it all // chack MAXN // check ll
  //did you check N=1? Did you mix up N,M?
}

• Subtask 1: 29 / 29
• Subtask 2: 37 / 37
• Subtask 3: 34 / 34