Submission #1290324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290324		yonatanl	Collecting Mushrooms (NOI18_collectmushrooms)	C++20	100 / 100	25 ms	19308 KiB

mushrooms

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

#define rep(i, s, e) for (ll i = s; i < e; i++)
#define upmax(a, b) a = max(a, b)
#define upmin(a, b) a = min(a, b)

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;

void solve() {
	ll n, m, D, K;
	cin >> n >> m >> D >> K;
	vvll arr(n, vll(m, 0));
	vpll mushrooms;
	rep(i, 0, n) {
		rep(j, 0, m) {
			char c;
			cin >> c;
			if (c == 'S') arr[i][j] = 1;
			else if (c == 'M') mushrooms.push_back({ i, j });
		}
	}
	vvll pref(n, vll(m));
	pref[0][0] = arr[0][0];
	rep(i, 1, m) pref[0][i] = pref[0][i - 1] + arr[0][i];
	rep(i, 1, n) pref[i][0] = pref[i - 1][0] + arr[i][0];
	rep(i, 1, n) {
		rep(j, 1, m) {
			pref[i][j] = pref[i][j - 1] + pref[i - 1][j] - pref[i - 1][j - 1] + arr[i][j];
		}
	}
	ll ans = 0;
	rep(i, 0, mushrooms.size()) {
		ll x = mushrooms[i].first;
		ll y = mushrooms[i].second;
		ll x1 = max((ll)0, x - D);
		ll x2 = min(n - 1, x + D);
		ll y1 = max((ll)0, y - D);
		ll y2 = min(m - 1, y + D);
		// Calc the sum in the rectangle:
		ll sum = pref[x2][y2];
		if (y1 > 0) sum -= pref[x2][y1 - 1];
		if (x1 > 0) sum -= pref[x1 - 1][y2];
		if (x1 > 0 && y1 > 0) sum += pref[x1 - 1][y1 - 1];
		if (sum >= K) ans++;
	}
	cout << ans << endl;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	solve();
}

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