제출 #659127

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
659127		beaconmc	Nautilus (BOI19_nautilus)	C++14	100 / 100	234 ms	460 KiB

nautilus

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast")

#pragma GCC target ("avx2")
typedef long long ll;
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
//#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)

bitset<512>  grid[501];

char ins[5001];

bitset<512> dp[2][512];

ll r,c,m;

bool valid(ll a, ll b){
	if (0<=a && a<r && 0<=b && b<c) return true;
	return false;
}

int main(){

	cin >> r >> c >> m;
	FOR(i,0,r){
		string temp; cin >> temp;
		FOR(j,0,c){
			if (temp[j]=='.') grid[i][j] = 1;
			else grid[i][j] = 0;
		}
	}
	string temp; cin >> temp;
	FOR(i,0,m) ins[i] = temp[i];

	FOR(i,0,r){
		FOR(j,0,c){
			dp[0][i][j] = grid[i][j];

		}
	}





	FOR(k,1,m+1){


		if (ins[k-1] == 'W' || ins[k-1] == '?'){
			FOR(i,0,r) dp[1][i] |= dp[0][i]>>1;
		}
		if (ins[k-1] == 'E' || ins[k-1] == '?'){
			FOR(i,0,r) dp[1][i] |= dp[0][i]<<1;
		}
		if (ins[k-1] == 'S' || ins[k-1] == '?'){
			FOR(i,1,r) dp[1][i] |= dp[0][i-1];
		}
		if (ins[k-1] == 'N' || ins[k-1] == '?'){
			FOR(i,0,r) dp[1][i] |= dp[0][i+1];
		}

		FOR(i,0,r) dp[1][i] &= grid[i];
		FOR(i,0,r) dp[0][i] = 0;
		FOR(i,0,r) dp[0][i] = dp[1][i];
		FOR(i,0,r) dp[1][i] = 0;
	}

	ll ans = 0;
	FOR(i,0,r){
		FOR(j,0,c){
			if (dp[0][i][j] == 1) ans++;
		}
	}
	cout << ans << endl;

}

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