Submission #164789

#TimeUsernameProblemLanguageResultExecution timeMemory
164789MSAADCollecting Mushrooms (NOI18_collectmushrooms)C++17
100 / 100
25 ms5276 KiB
#include<bits/stdc++.h>
using namespace std;
char c;
int r,w,d,k;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>r>>w>>d>>k;
	bool check[r+1][w+1];
	int diff[r+1][w+1];
	for(int i=0;i<r;i++){
		for(int j=0;j<w;j++){
			diff[i][j]=0;
			check[i][j]=false;
		}
	}
	for(int i=0;i<r;i++){
		for(int j=0;j<w;j++){
			cin>>c;
			if(c=='M')check[i][j]=true;
			else if(c=='S'){
				int up=max(0,i-d);
				int down=min(r-1,i+d);
				int left=max(0,j-d);
				int right=min(w-1,j+d);
				diff[up][left]++;
				diff[up][right+1]--;
				diff[down+1][left]--;
				diff[down+1][right+1]++;
			}
		}
	}
	for(int i=1;i<w;i++) diff[0][i]+=diff[0][i-1];
	for(int i=1;i<r;i++) diff[i][0]+=diff[i-1][0];
	for(int i=1;i<=r;i++){
		for(int j=1;j<=w;j++)
			diff[i][j]+=diff[i-1][j]+diff[i][j-1]-diff[i-1][j-1];
	}
//	for(int i=0;i<r;i++){
//		for(int j=0;j<w;j++)
//			cout<<diff[i][j]<<" ";
//		cout<<endl;
//	}
	int ans=0;
	for(int i=0;i<r;i++)
		for(int j=0;j<w;j++)
			if(check[i][j]==true && diff[i][j]>=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...