Submission #1168746

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168746		lufychop	Collecting Mushrooms (NOI18_collectmushrooms)	C++20	19 / 100	23 ms	21224 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<pair<long long,long long>> v;
	cin>>r>>c>>d>>k;
	vector<long long> ps((r+2)*(c+2),0);
	c++;
	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]=1;
			}
			else if(s[j-1]=='M')
			{
				v.push_back({i,j});
			}
		}
	}
	for(int i=1;i<=r;i++)
	{
		for(int j=1;j<c;j++)
		{
			//cout<<"("<<i<<","<<j<<") "<<i*(c+1)+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];
			//cout<<ps[i*c+j]<<" ";
		}
		//cout<<"\n";
	}
	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=min(y2,c-1);
		//cout<<x2<<" "<<y2<<" "<<ps[x2*c+y2]<<"\n";
		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.

4 4 4 1
....
.M..
..MM
...S
*/

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