Submission #807412

#	Time	Username	Problem	Language	Result	Execution time	Memory
807412		MODDI	Nautilus (BOI19_nautilus)	C++17	100 / 100	186 ms	728 KiB

nautilus

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
int r, c, n;
string str;
bitset<501> sea[501];
bitset<501> dp[2][501];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>r>>c>>n;
	memset(dp, 0, sizeof dp);
	memset(sea, 0, sizeof sea);
	for(int i = 0; i < r; i++){
		string s;
		cin>>s;
		for(int j = 0; j < c; j++){
			if(s[j] == '.'){
				sea[i][j] = 1;
				dp[0][i][j] = 1;
			}
		}
	}
	cin>>str;
	for(int step = 1; step <= n; step++){
		for(int i = 0; i < r; i++){
			dp[step%2][i] = 0;
		}
		for(int i = 0; i < r; i++){
			if (str[step - 1] == 'E' || str[step - 1] == '?') dp[step % 2][i] |= (dp[(step - 1) % 2][i] << 1 & sea[i]);
            if (str[step - 1] == 'W' || str[step - 1] == '?') dp[step % 2][i] |= (dp[(step - 1) % 2][i] >> 1 & sea[i]);
            if ((str[step - 1] == 'S' || str[step - 1] == '?') && i > 0) dp[step % 2][i] |= (dp[(step - 1) % 2][i - 1] & sea[i]);
            if ((str[step - 1] == 'N' || str[step - 1] == '?') && i < n - 1) dp[step % 2][i] |= (dp[(step - 1) % 2][i + 1] & sea[i]);
		}
	}
	ll ans = 0;
	for(int i = 0; i < r; i++){
		ans += dp[n%2][i].count();
	}
	cout<<ans<<endl;
	return 0;
}

Compilation message (stderr)

nautilus.cpp: In function 'int main()':
nautilus.cpp:19:27: warning: 'void* memset(void*, int, size_t)' clearing an object of non-trivial type 'class std::bitset<501>'; use assignment or value-initialization instead [-Wclass-memaccess]
   19 |  memset(sea, 0, sizeof sea);
      |                           ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:66,
                 from nautilus.cpp:1:
/usr/include/c++/10/bitset:751:11: note: 'class std::bitset<501>' declared here
  751 |     class bitset
      |           ^~~~~~

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