Submission #1116561

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116561		xnqs	Nautilus (BOI19_nautilus)	C++17	100 / 100	64 ms	1116 KiB

nautilus

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi2,popcnt,lzcnt")

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <cstring>
#include <bitset>

int x, y, p;
char arr[505][505];
char moves[5005];
std::bitset<505> dp[2][505];
std::bitset<505> row[505];

void solve_dp() {
	for (int i = 0; i < x; i++) {
		dp[0][i] = row[i];
	}

	for (int pos = 1; pos <= p; pos++) {
		int curr = pos&1;
		int last = (pos-1)&1;
		for (int i = 0; i < x; i++) {
			dp[curr][i].reset();
			switch (moves[pos-1]) {
			case 'N':
				dp[curr][i] = dp[last][i+1] & row[i];
				break;
			case 'S':
				dp[curr][i] = dp[last][i-1] & row[i];
				break;
			case 'E':
				dp[curr][i] = (dp[last][i]<<1) & row[i];
				break;
			case 'W':
				dp[curr][i] = (dp[last][i]>>1) & row[i];
				break;
			default:
				dp[curr][i] |= dp[last][i+1];
				dp[curr][i] |= dp[last][i-1];
				dp[curr][i] |= (dp[last][i]<<1);
				dp[curr][i] |= (dp[last][i]>>1);
				dp[curr][i] &= row[i];
				break;
			}
		}
	}
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cin >> x >> y >> p;
	for (int i = 0; i < x; i++) {
		std::cin >> arr[i];
		for (int j = 0; j < y; j++) {
			row[i][j] = ((arr[i][j]=='.') ? 1 : 0);
		}
	}
	std::cin >> moves;

	solve_dp();
	int ret = 0;
	for (int i = 0; i < x; i++) {
		ret += dp[p&1][i].count();
	}

	std::cout << ret << "\n";
}

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