Submission #828926

#	Time	Username	Problem	Language	Result	Execution time	Memory
828926		NK_	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	100 / 100	9 ms	7272 KiB

mushrooms

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
 
using namespace std;
 
#define nl '\n'
#define pb push_back 
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
 
template<class T> using V = vector<T>;
using vi = V<int>;
using ll = long long;
using pi = pair<int, int>;
using vpi = V<pi>;
using vl = V<ll>;
using db = double;

const int INF = 1e9 + 10;

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int N, M, D, K; cin >> N >> M >> D >> K;
	V<string> A(N); for(auto& x : A) cin >> x;

	V<vi> P(N + 1, vi(M + 1));

	for(int r = 0; r < N; r++) {
		for(int c = 0; c < M; c++) if (A[r][c] == 'S') {
			int tr = max(0, r - D), tc = max(0, c - D);
			int br = min(N - 1, r + D) + 1, bc = min(M - 1, c + D) + 1;

			P[tr][tc]++;
			P[tr][bc]--;
			P[br][tc]--;
			P[br][bc]++;
		}
	}

	int ans = 0;
	for(int r = 0; r < N; r++) {
		for(int c = 0; c < M; c++) {
			if (r) P[r][c] += P[r-1][c];
			if (c) P[r][c] += P[r][c-1];
			if (r && c) P[r][c] -= P[r-1][c-1];

			if (A[r][c] == 'M') ans += (P[r][c] >= K);
		}
	}
	cout << ans << nl;

	exit(0-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