Submission #141077

#	Time	Username	Problem	Language	Result	Execution time	Memory
141077		tincamatei	Collecting Mushrooms (NOI18_collectmushrooms)	C++14	100 / 100	47 ms	7488 KiB

mushrooms

#include <bits/stdc++.h>

using namespace std;

int main() {
	int R, C, D, K;

	vector<string> matr;
	vector<vector<int> > smen;
	
	cin >> R >> C >> D >> K;
	for(int i = 0; i < R; ++i) {
		string str;
		cin >> str;
		matr.push_back(str);
	}

	smen = vector<vector<int> >(R + 1, vector<int>(C + 1, 0));

	for(int l = 0; l < R; ++l)
		for(int c = 0; c < C; ++c)
			if(matr[l][c] == 'S') {
				int l1, c1, l2, c2;
				l1 = max(0, l - D);
				l2 = min(R, l + D + 1);
				c1 = max(0, c - D);
				c2 = min(C, c + D + 1);

				smen[l1][c1]++;
				smen[l1][c2]--;
				smen[l2][c1]--;
				smen[l2][c2]++;
			}
	
	int rez = 0;
	for(int l = 0; l < R; ++l) {
		int p = 0;
		for(int c = 0; c < C; ++c) {
			p += smen[l][c];
			smen[l + 1][c] += smen[l][c];

			if(matr[l][c] == 'M' && p >= K)
				++rez;
		}
	}

	printf("%d", rez);
	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