Submission #130794

#	Time	Username	Problem	Language	Result	Execution time	Memory
130794		nandonathaniel	Collecting Mushrooms (NOI18_collectmushrooms)	C++14	100 / 100	38 ms	17168 KiB

mushrooms

#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;
}

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