Submission #783677

#	Time	Username	Problem	Language	Result	Execution time	Memory
783677		stefdasca	Collecting Mushrooms (NOI18_collectmushrooms)	C++14	100 / 100	13 ms	7636 KiB

mushrooms

#include <bits/stdc++.h>

using namespace std;

int main()
{
	int n, m, d, k;
	cin >> n >> m >> d >> k;
	
	char grid[n+1][m+1];
	for(int i = 1; i <= n; i++)
		cin >> (grid[i] + 1);
	
	int sp[n+2][m+2];
	for(int i = 0; i <= n+1; i++)
		for(int j = 0; j <= m+1; j++)
			sp[i][j] = 0;
	
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
		{
			if(grid[i][j] == 'S')
			{
				int La = max(1, i-d);
				int Ca = max(1, j-d);
				int Lb = min(n, i+d);
				int Cb = min(m, j+d);
				sp[La][Ca]++;
				sp[La][Cb+1]--;
				sp[Lb+1][Ca]--;
				sp[Lb+1][Cb+1]++;
			}
		}
		
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			sp[i][j] = sp[i][j] + sp[i-1][j] + sp[i][j-1] - sp[i-1][j-1];
	
	int ans = 0;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			if(sp[i][j] >= k && grid[i][j] == 'M')
				ans++;
	
	cout << ans;
	return 0;
}

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