Submission #1334531

#TimeUsernameProblemLanguageResultExecution timeMemory
1334531NurislamCollecting Mushrooms (NOI18_collectmushrooms)C++20
100 / 100
12 ms16600 KiB
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int inf = 1e17, mod = 998244353, N = 5e6+5;


mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rnd(l, r) uniform_int_distribution<int>(l, r)(rng)

int bp (int a, int n, int md) {
	int res = 1, p = a;
	while(n > 0) {
		if(n & 1) res = res * p % md;
		p = p * p % md;
		n >>= 1;
	};
	return res;
};


int gcd(int a, int b, int & x1, int & y1) {
	if(b == 0) {
		x1 = 1;
		y1 = 0;
		return a;
	};
	int x = 0, y = 0;
	int g = gcd(b, a%b, y, x);
	// b * y + a % b * x = g
	// b * y + a * x - b * (a/b)*x = g
	// a * x + b * (y - (a/b)*x) = g
	x1 = x;
	y1 = y - (a/b) * x;
	return g;
};

void solve() {
	int n, m, d, k;
	cin >> n >> m >> d >> k;
	
	vector<string> s(n);
	for(auto&i : s) cin >> i;
	
	vector<vector<int>> p(n+2, vector<int> (m+2));
	
	for(int i = 1; i <= n; i ++ ) {
		for(int j = 1; j <= m; j ++ ) {
			if(s[i-1][j-1] != 'S')continue;
			
			int x = i-d, y = j-d;
			x = max(x, 1ll);y = max(y, 1ll);
			int x1 = i+d+1, y1 = j+d+1;
			x1 = min(x1, n+1); y1 = min(y1, m+1);
			p[x][y] ++;
			p[x1][y] -- ;
			p[x][y1] -- ;
			p[x1][y1] ++ ;
		};
	};
	
	for(int i = 1; i <= n; i ++ ) 
		for(int j = 1; j <= m; j ++ ) 
			p[i][j] = (p[i][j] + p[i-1][j] + p[i][j-1] - p[i-1][j-1]);
			
	int ans = 0;
	for(int i = 1; i <= n; i ++ ) 
		for(int j = 1; j <= m; j ++ ) 
			ans += (s[i-1][j-1] == 'M' && p[i][j] >= k);
		
	cout << ans << '\n';
};


signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int tt = 1;
	//cin >> tt; 
	
	while( tt -- ) {
		solve();
	};
}; 
















#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...