Submission #1082336

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082336		vuavisao	Collecting Mushrooms (NOI18_collectmushrooms)	C++14	100 / 100	15 ms	29788 KiB

mushrooms

#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

using ll = long long;

const int N = 500'000 + 10;

int numRows, numCols, dist, cnt;
string s[N];

vector<vector<int>> pred;

int32_t main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr); std::cout.tie(nullptr);
	cin >> numRows >> numCols >> dist >> cnt;
	pred.resize(numRows + 5, vector<int>(numCols + 5, 0));
	for (int i = 1; i <= numRows; ++ i) {
		cin >> s[i]; s[i] = ' ' + s[i];
		for (int j = 1; j <= numCols; ++ j) {
			if (s[i][j] == 'S') {
				int le = max(1, j - dist);
				int ri = min(numCols, j + dist);
				int up = max(1, i - dist);
				int down = min(numRows, i + dist);
				++ pred[up][le];
				-- pred[up][ri + 1];
				-- pred[down + 1][le];
				++ pred[down + 1][ri + 1];
			}
		}
	}
	int res = 0;
	for (int i = 1; i <= numRows; ++ i) {
		for (int j = 1; j <= numCols; ++ j) {
			pred[i][j] += pred[i - 1][j] + pred[i][j - 1] - pred[i - 1][j - 1];
			if (s[i][j] == 'M' && pred[i][j] >= cnt) ++ res;
		}
	}
	cout << res;
	return (0 ^ 0);
}

/// Code by vuavisao

• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 18 / 18
• Subtask 4: 23 / 23
• Subtask 5: 19 / 19
• Subtask 6: 21 / 21