Submission #590582

#	Time	Username	Problem	Language	Result	Execution time	Memory
590582		starchan	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	100 / 100	17 ms	12552 KiB

mushrooms

#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;
}	

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