Submission #522714

#	Time	Username	Problem	Language	Result	Execution time	Memory
522714		nhphucqt	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	100 / 100	30 ms	39024 KiB

mushrooms

#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;
}

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