Submission #643719

#	Time	Username	Problem	Language	Result	Execution time	Memory
643719		amoorj	Nautilus (BOI19_nautilus)	C++17	66 / 100	1076 ms	14284 KiB

nautilus

#pragma GCC optimize ("O3,unroll-loops")
#pragma GCC target ("avx2,bmi,bmi2,popcnt")
#include <bits/stdc++.h>
#define F first
#define pb push_back
#define sz size()
#define S second
using namespace std;
typedef long long int ll;

const int N = 505, M = 5005;
int r,c,m;
string wef,s[N];
bitset<N*N> dp[M];

int get(int x,int y){
	return (y * c + x);
}
pair<int,int> cor(int i){
	return make_pair(i/c,i%c);
}
inline void init(){
}
inline void input(){
	cin >> r >> c >> m;
	for(int i=0;i<r;i++)
		cin >> s[i];
	cin >> wef;
}
inline void solve(){
	for(int i=0;i<r*c;i++){
		pair<int,int> few = cor(i);
		int x = few.S, y = few.F;
		dp[0][i] = (s[y][x] == '.');
	}
	for(int j=1;j<=m;j++){
		for(int i=0;i<r*c;i++){
			pair<int,int> few = cor(i);
			int x = few.S, y = few.F;
			if(s[y][x] == '#'){
				dp[j][i] = false;
				continue;
			}
			if((wef[j-1] == 'S' || wef[j-1] == '?') && y-1 >= 0)
				dp[j][i] = dp[j][i] | dp[j-1][get(x,y-1)];
			
			if((wef[j-1] == 'N' || wef[j-1] == '?') && y+1 < r)
				dp[j][i] = dp[j][i] | dp[j-1][get(x,y+1)];
			
			if((wef[j-1] == 'E' || wef[j-1] == '?') && x-1 >= 0)
				dp[j][i] = dp[j][i] | dp[j-1][get(x-1,y)];
			
			if((wef[j-1] == 'W' || wef[j-1] == '?') && x+1 < c)
				dp[j][i] = dp[j][i] | dp[j-1][get(x+1,y)];
		}
	}
	int cnt = 0;
	for(int i=0;i<r*c;i++){
//		if(i % c == 0)
//			cout << endl;
//		cout << dp[i][m];
		cnt += dp[m][i];
	}
	cout << cnt;
}
int main(){
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
	init();
	int queries = 1;
//	cin >> queries;
	while(queries--){
		input();
		solve();
	}
	return 0;
}

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