Submission #171551

#	Time	Username	Problem	Language	Result	Execution time	Memory
171551		dndhk	Nautilus (BOI19_nautilus)	C++14	100 / 100	261 ms	1308 KiB

nautilus

#include <bits/stdc++.h>

#define all(v) (v).begin(), (v).end()
#define sortv(v) sort(all(v))
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define test 1
#define TEST if(test)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

const int MOD = 1000000007; // 998244353
const int INF = 2e9;
const ll INFLL = 1e18;
const int MAX_N = 500;

int N, M, Q;
string arr[MAX_N+1];
string str;
bitset<MAX_N> stage[MAX_N+1], dp[2][MAX_N+1], bt;

int main(){
	scanf("%d%d%d", &N, &M, &Q);	
	for(int i=0; i<N; i++){
		cin>>arr[i];
		for(int j=0; j<M; j++){
			if(arr[i][j]=='.'){
				stage[i][j] = 1;
				dp[0][i][j] = 1;
			}
		}
	}
	for(int i=0; i<M; i++){
		bt[i] = 1;
	}
	cin>>str;
	for(int i=0; i<Q; i++){
		if(str[i]=='N'){
			for(int i=0; i<N-1; i++){
				dp[0][i] = (stage[i] & dp[0][i+1]);
			}
			dp[0][N-1].reset();
		}else if(str[i]=='E'){
			for(int i=0; i<N; i++){
				dp[0][i] = ((dp[0][i]<<1) & stage[i]);
			}
		}else if(str[i]=='S'){
			for(int i=N; i>0; i--){
				dp[0][i] = (stage[i] & dp[0][i-1]);
			}
			dp[0][0].reset();
		}else if(str[i]=='W'){
			for(int i=0; i<N; i++){
				dp[0][i] = ((dp[0][i]>>1) & stage[i]);
			}
		}else{
			for(int i=0; i<N; i++){
				dp[1][i] = ((dp[0][i]>>1) | (dp[0][i]<<1));
				if(i!=0){
					dp[1][i] = (dp[1][i] | dp[0][i-1]);
				}if(i!=N-1){
					dp[1][i] = (dp[1][i] | dp[0][i+1]);
				}
				dp[1][i] = (dp[1][i] & stage[i]);
			}
			for(int i=0; i<N; i++){
				dp[0][i] = dp[1][i];
			}
		}
		for(int i=0; i<N; i++){
			dp[0][i] = (dp[0][i] & bt);
			//for(int j=0; j<M; j++){
			//	cout<<dp[0][i][j];
			//}cout<<endl;
			//cout<<dp[0][i].to_string()<<endl;
		}//cout<<endl;
	}
	int ans=0;
	for(int i=0; i<N; i++){
		for(int j=0; j<M; j++){
			ans+=dp[0][i][j];
		}
	}
	cout<<ans;
	return 0;
}

Compilation message (stderr)

nautilus.cpp: In function 'int main()':
nautilus.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &M, &Q); 
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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