Submission #164786

#	Time	Username	Problem	Language	Result	Execution time	Memory
164786		MSAAD	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	60 / 100	28 ms	3448 KiB

mushrooms

#include<bits/stdc++.h>
using namespace std;
char c[501][501];
bool check[501][501];
int diff[501][501];
int r,w,d,k;
int main(){
	cin>>r>>w>>d>>k;
	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[i][j];
			if(c[i][j]=='M')check[i][j]=true;
			else if(c[i][j]=='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;
}
				
			

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