Submission #535111

#	Time	Username	Problem	Language	Result	Execution time	Memory
535111		new_acc	Nautilus (BOI19_nautilus)	C++14	100 / 100	144 ms	672 KiB

nautilus

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=510;
bitset<N>t[N];
bitset<N>t2[N];
bitset<N>xd[N];
void solve(){
	int n,m,d;
	cin>>n>>m>>d;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char a;
			cin>>a;
			if(a=='.') t[i][j]=1,xd[i][j]=1;
		}
	}
	string s;
	cin>>s;
	s="#"+s;
	for(int j=1;j<=d;j++){
		if(s[j]=='W') for(int i=1;i<=n;i++) t[i]>>=1,t[i]&=xd[i];
		if(s[j]=='E') for(int i=1;i<=n;i++) t[i]<<=1,t[i]&=xd[i];
		if(s[j]=='N'){
			for(int i=1;i<n;i++) t[i]=t[i+1],t[i]&=xd[i];
			t[n].reset();
		}
		if(s[j]=='S'){
			for(int i=n;i>=2;i--) t[i]=t[i-1],t[i]&=xd[i];
			t[1].reset();
		}
		if(s[j]=='?'){
			t2[1].reset();
			for(int i=2;i<=n;i++) t2[i]=t[i-1];
			for(int i=n-1;i>=1;i--) t2[i]|=t[i+1];
			for(int i=1;i<=n;i++) t2[i]|=(t[i]<<1),t2[i]|=(t[i]>>1),t2[i]&=xd[i];
			for(int i=1;i<=n;i++) t[i]=t2[i];
		}
	}
	int res=0;
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(t[i][j]) res++;
	cout<<res<<"\n";
}
int main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	solve();
}

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