Submission #926062

#	Time	Username	Problem	Language	Result	Execution time	Memory
926062		vjudge1	Nautilus (BOI19_nautilus)	C++17	100 / 100	163 ms	1132 KiB

nautilus

#include <bits/stdc++.h>

using namespace std;

#define all(a) a.begin(),a.end()
#define pb push_back
#define vt vector
#define endl '\n'
typedef long long ll;

const ll mod=1e9+7;
const ll inf=mod;
const int N=5e6+4;

int n,m,k;
char c[600][600];
bitset<600> dp[2][600],cons[600];

void solve(){
	cin>>n>>m>>k;
	for(int i=1; i<=n; ++i){
		for(int j=1; j<=m; ++j){
			cin>>c[i][j];
			if(c[i][j]!='#') dp[0][i][j]=1;
			dp[0][0][j]=0;
			dp[0][n+1][j]=0;
		}
		dp[0][i][0]=dp[0][i][m+1]=0;
		cons[i]=dp[0][i];
		dp[1][i]=dp[0][i];
	}
	string s;
	cin>>s;
	s='#'+s;
	for(int x=1; x<=k; ++x){
		for(int i=1; i<=n; ++i){
			if(s[x]=='N') dp[1][i]&=dp[0][i+1];
			if(s[x]=='S') dp[1][i]&=dp[0][i-1];
			if(s[x]=='W') dp[1][i]&=(dp[0][i]>>1);
			if(s[x]=='E') dp[1][i]&=(dp[0][i]<<1);
			if(s[x]=='?') dp[1][i]&=((dp[0][i]>>1)|(dp[0][i]<<1)|dp[0][i+1]|dp[0][i-1]);
		}
		for(int i=1; i<=n; ++i){
			dp[0][i]=dp[1][i];
			dp[1][i]=cons[i];
		}
	}
	int ans=0;
	for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j){
		ans+=dp[0][i][j];
	}
	cout<<ans<<endl;
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int tt=1;
//	cin>>tt;
	while(tt--) {
		solve();
	}
}

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