제출 #130794

#제출 시각아이디문제언어결과실행 시간메모리
130794nandonathanielCollecting Mushrooms (NOI18_collectmushrooms)C++14
100 / 100
38 ms17168 KiB
#include<bits/stdc++.h>
using namespace std;

vector<pair<int,int> > mushroom;

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int r,c,d,k;
	cin >> r >> c >> d >> k;
	char arr[r+5][c+5];
	int pref[r+5][c+5];
	memset(pref,0,sizeof(pref));
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			cin >> arr[i][j];
			if(arr[i][j]=='S')pref[i][j]++;
			if(i)pref[i][j]+=pref[i-1][j];
			if(j)pref[i][j]+=pref[i][j-1];
			if(i&&j)pref[i][j]-=pref[i-1][j-1];
			if(arr[i][j]=='M')mushroom.push_back({i,j});
		}
	}
	int ans=0;
	for(auto p : mushroom){
		//area nya itu p.first-d p.second
		int kananx=min(p.first+d,r),kanany=min(p.second+d,c),kirix=max(p.first-d,1),kiriy=max(p.second-d,1);
		int many=pref[kananx][kanany]-pref[kirix-1][kanany]-pref[kananx][kiriy-1]+pref[kirix-1][kiriy-1];
		if(many>=k)ans++;
	}
	cout << ans << endl;
	return 0;
}

#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...