Submission #1262371

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262371		PlayVoltz	Collecting Mushrooms (NOI18_collectmushrooms)	C++20	100 / 100	20 ms	15780 KiB

mushrooms

#include <bits/stdc++.h>
using namespace std;

int main(){
	int r, c, n, m;
	cin>>r>>c>>n>>m;
	string s;
	vector <pair<int, int> > mushrooms;
	vector<vector<int> > vect;
	vect.resize(r+1, vector<int>(c+1, 0));
	vector <vector<int> > psum;
	psum.resize(r+1, vector<int>(c+1, 0));
	for (int i=0; i<r; ++i){
		cin>>s;
		for (int j=0; j<c; ++j){
			if (s[j]=='M'){
				mushrooms.push_back(make_pair(i+1, j+1));
			}
			else if (s[j]=='S'){
				++vect[i+1][j+1];
			}
			vect[i+1][j+1]+=vect[i+1][j];
		}
	}
	for (int j=1; j<=c; ++j){
		for (int i=1; i<=r; ++i){
			psum[i][j] = psum[i-1][j]+vect[i][j];
		}
	}
	int f = 0;
	for (auto mush:mushrooms){
		int count = psum[min(mush.first+n, r)][min(mush.second+n, c)]+psum[max(mush.first-n-1, 0)][max(mush.second-n-1, 0)]-psum[max(mush.first-n-1, 0)][min(mush.second+n, c)]-psum[min(mush.first+n, r)][max(mush.second-n-1, 0)];
		if (count>=m){
			++f;
		}
	}
	cout<<f;
}

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