Submission #1262371

#TimeUsernameProblemLanguageResultExecution timeMemory
1262371PlayVoltzCollecting Mushrooms (NOI18_collectmushrooms)C++20
100 / 100
20 ms15780 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...