Submission #522714

#TimeUsernameProblemLanguageResultExecution timeMemory
522714nhphucqtCollecting Mushrooms (NOI18_collectmushrooms)C++17
100 / 100
30 ms39024 KiB
#include <bits/stdc++.h>

using namespace std;

const int N = 5e5+7;
int numRow, numCol, maxDist, minNum;
vector<int> a[N];
string s[N];

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	#ifdef NHPHUCQT
	freopen("demo.inp", "r", stdin);
	freopen("demo.out", "w", stdout);
	#endif // NHPHUCQT

	cin >> numRow >> numCol >> maxDist >> minNum;
	for (int i = 0; i <= numRow+3; ++i) {
		a[i].resize(numCol+3, 0);
	}
	for (int i = 1; i <= numRow; ++i) {
		cin >> s[i];
		s[i] = '0' + s[i];
	}
	for (int i = 1; i <= numRow; ++i)
	for (int j = 1; j <= numCol; ++j) {
		// s[i][j]
		if (s[i][j] == 'S') {
			int x = max(1, i - maxDist);
			int y = max(1, j - maxDist);
			int u = min(numRow, i + maxDist);
			int v = min(numCol, j + maxDist);
			a[x][y]++;
			a[x][v+1]--;
			a[u+1][y]--;
			a[u+1][v+1]++;
		}
	}
	for (int i = 1; i <= numRow; ++i)
	for (int j = 1; j <= numCol; ++j) {
		a[i][j] += a[i][j-1];
	}
	for (int j = 1; j <= numCol; ++j)
	for (int i = 1; i <= numRow; ++i) {
		a[i][j] += a[i-1][j];
	}
	int res = 0;
	for (int i = 1; i <= numRow; ++i)
	for (int j = 1; j <= numCol; ++j) {
		if (s[i][j] == 'M') {
			res += a[i][j] >= minNum;
		}
	}
	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...