Submission #961425

#TimeUsernameProblemLanguageResultExecution timeMemory
961425vjudge1Collecting Mushrooms (NOI18_collectmushrooms)C++17
100 / 100
30 ms21276 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...