Submission #1168736

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168736		lufychop	Collecting Mushrooms (NOI18_collectmushrooms)	C++20	0 / 100	8 ms	5348 KiB

mushrooms

#include <bits/stdc++.h>

using namespace std;

int main(void)
{
	long long r,c,d,k,ans=0,x1,y1,x2,y2;
	vector<long long> ps(500002,0);
	vector<pair<long long,long long>> v;
	cin>>r>>c>>d>>k;
	for(int i=1;i<=r;i++)
	{
		string s;
		cin>>s;
		for(int j=1;j<=c;j++)
		{
			if(s[j-1]=='S')
			{
				ps[i*c+j]++;
			}
			else if(s[j-1]=='M')
			{
				v.push_back({i,j});
			}
			ps[i*c+j]=ps[i*c+j]+ps[i*c+j-c]+ps[i*c+j-1]-ps[i*c+j-c-1];
		}
	}
	for(int i=0;i<v.size();i++)
	{
		x1=v[i].first-d;
		x2=v[i].first+d;
		y1=v[i].second-d;
		y2=v[i].second+d;
		x1=max(x1,(long long)0);
		x2=min(x2,r);
		y1=max(y1,(long long)0);
		y2=max(y2,c);
		if(ps[x2*c+y2]-ps[x2*c+y1]-ps[x1*c+y2]+ps[x1*c+y1]>=k)
		{
			ans++;
		}
	}
	cout<<ans;
	return 0;
}
/*
5 5 1 1
....M
.M...
..S..
.S...
...M.
*/

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