Submission #961425

#	Time	Username	Problem	Language	Result	Execution time	Memory
961425		vjudge1	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	100 / 100	30 ms	21276 KiB

mushrooms

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ent "\n"

const int maxn = 5e5 + 100;
const ll INF = (ll)1e18 + 100;
const int inf = 1e9 + 100;
const int MOD = 1e9 + 7;
const int maxl = 30;
const int P = 31;

int n, m, d, k;
vector<int> pref[maxn];

void test(){
	cin >> n >> m >> d >> k;
	pref[0] = vector<int>(m + 10, 0);
	vector<pii> v, ad;
	for(int i = 1; i <= n; i++){
		pref[i] = pref[i-1];
		for(int j = 1; j <= m; j++){
			char c; cin >> c;
			if(c == 'M') v.push_back({i, j});
			else if(c == 'S') ad.push_back({i, j});
		}
	}
	for(auto [i, j]: ad){
		int a = max(1, i - d);
		int x = min(n, i + d);
		int b = max(1, j - d);
		int y = min(m, j + d);
		pref[a][b]++;
		pref[a][y+1]--;
		if(x < n){
			pref[x+1][b]--;
			pref[x+1][y+1]++;
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			pref[i][j] += pref[i-1][j];
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			pref[i][j] += pref[i][j-1];
		}
	}
	int ans = 0;
	for(auto [i, j]: v){
		if(pref[i][j] >= k) ans++;
	}
	cout << ans << ent;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t = 1; t = 1;
	while(t--) test();
	cout << ent;
}

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