Submission #1290318

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290318		yonatanl	Collecting Mushrooms (NOI18_collectmushrooms)	C++20	42 / 100	2095 ms	6060 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 r, c, D, K;
	cin >> r >> c >> D >> K;
	vpll arrS; // Store sprinkles positions
	vpll arrM; // Store mushrooms positions
	rep(i, 0, r) {
		rep(j, 0, c) {
			char c;
			cin >> c;
			if (c == 'S') {
				arrS.push_back({ i, j });
			}
			else if (c == 'M') {
				arrM.push_back({ i, j });
			}
		}
	}
	ll n = arrS.size(); // Number of sprinkles
	ll m = arrM.size(); // Number of mushrooms
	sort(arrS.begin(), arrS.end());
	sort(arrM.begin(), arrM.end());
	ll x = arrM[0].first;
	ll y = arrM[0].second;
	multiset<ll> s;
	ll left = -1, right = -1;
	rep(i, 0, n) {
		if (abs(x - arrS[i].first) <= D) {
			if (left == -1) left = i;
			right = i;
		}
	}
	vll ans(m);
	rep(i, max(left, (ll)0), min(n, right + 1)) {
		if (abs(y - arrS[i].second) <= D) {
			ans[0]++;
		}
	}
	rep(i, 1, m) {
		x = arrM[i].first, y = arrM[i].second;
		//cout << "x = " << x << " y = " << y << endl;
		ll idx = max(left, (ll)0);
		while (idx < n) {
			if (abs(x - arrS[idx].first) > D) {
				idx++;
			}
			else break;
		}
		left = idx;
		idx = right + 1;
		while (idx < n) {
			if (abs(x - arrS[idx].first) <= D) {
				idx++;
			}
			else break;
		}
		right = idx - 1;
		//cout << "left = " << left << " right = " << right << endl;
		rep(j, max(left, (ll)0), min(n, right + 1)) {
			if (abs(y - arrS[j].second) <= D) {
				ans[i]++;
			}
		}
	}
	ll res = 0;
	rep(i, 0, m) {
		//cout << ans[i] << ' ';
		if (ans[i] >= K) {
			res++;
		}
	}
	//cout << endl;
	cout << res << endl;
}

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

	solve();
}

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