Submission #1082337

#TimeUsernameProblemLanguageResultExecution timeMemory
1082337vuavisaoCollecting Mushrooms (NOI18_collectmushrooms)C++14
100 / 100
14 ms29788 KiB
#include <bits/stdc++.h>
using namespace std;

const int N = (int) 5e5 + 10;

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

vector<vector<int>> pred;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); 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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...