Submission #161127

#	Time	Username	Problem	Language	Result	Execution time	Memory
161127		Berted	Collecting Mushrooms (NOI18_collectmushrooms)	C++14	100 / 100	72 ms	15308 KiB

mushrooms

#include <iostream>
#include <vector>
#define ll long long
using namespace std;
ll r,c,d,k,to=0;
vector<vector<ll>> mp;
vector<string> tmp;
void set(int y,int x,int d)
{
	int tly = max(y-d,1),tlx = max(x-d,1);
	int bry = min(y+d,(int)r),brx = min(x+d,(int)c);
	//cout<<tly<<" "<<tlx<<" "<<bry<<" "<<brx<<"\n";
	mp[tly][tlx] ++;
	mp[tly][brx+1] --;
	mp[bry+1][tlx] --;
	mp[bry+1][brx+1] ++; 
}
int main()
{
	cin>>r>>c>>d>>k;
	for (int i=0;i<r+2;i++)
	{
		mp.push_back(vector<ll>());
		for (int j=0;j<c+2;j++)
		{
			mp[i].push_back(0);
		}
	}
	string trsh = "";
	for (int i=0;i<c;i++)
	{
		trsh+=" ";
	}
	tmp.push_back(trsh);
	for (int i=0;i<r;i++)
	{
		string tp;cin>>tp;
		tp=" "+tp;tp+=" ";
		tmp.push_back(tp);
	}
	tmp.push_back(trsh);
	for (int i=1;i<=r;i++)
	{
		for (int j=1;j<=c;j++)
		{
			if (tmp[i][j]=='S') {set(i,j,d);}
		}
	}
	for (int i=1;i<=r;i++)
	{
		for (int j=1;j<=c;j++)
		{
			mp[i][j] += mp[i-1][j] + mp[i][j-1] - mp[i-1][j-1];
			if (tmp[i][j]=='M'&&mp[i][j]>=k) {to++;}
		}
	}
	cout<<to<<"\n";
	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