Submission #590582

#TimeUsernameProblemLanguageResultExecution timeMemory
590582starchanCollecting Mushrooms (NOI18_collectmushrooms)C++17
100 / 100
17 ms12552 KiB
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define MX (int)3e5+5
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
signed main()
{
	fast();
	int n, m, D, k;
	cin >> n >> m >> D >> k;
	int diff[n+1][m+1];
	for(int i = 0; i <= n; i++)
	{
		for(int j = 0; j <= m; j++)
			diff[i][j] = 0;
	}
	int grid[n][m];
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
		{
			char t;
			cin >> t;
			grid[i][j] = t-'M';
			if(t=='S')
			{
				int a = max(i-D, 0ll);
				int b = max(j-D, 0ll);
				int c = min(i+D, n-1);
				int d = min(j+D, m-1);
				diff[a][b]++;
				diff[c+1][d+1]++;
				diff[a][d+1]--;
				diff[c+1][b]--;
			}
		}
	}
	for(int i = 0; i < n; i++)
	{
		for(int j = 1; j < m; j++)
			diff[i][j]+=diff[i][j-1];
	}
	int ans = 0;
	for(int i = 1; i < n; i++)
	{
		for(int j = 0; j < m; j++)
			diff[i][j]+=diff[i-1][j];
	}	
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
		{
			if(diff[i][j] >= k && grid[i][j] == 0)
				ans++;
		}
	}
	cout << ans;
	return 0;
}	
#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...