Submission #676475

#	Time	Username	Problem	Language	Result	Execution time	Memory
676475		penguin133	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	100 / 100	38 ms	9580 KiB

mushrooms

#include <bits/stdc++.h>
using namespace std;

int main(){
	int r,c,d,k;
	cin >> r >> c >> d >> k;
	char g[r+1][c+1];
	int prefix[r+1][c+1];
	int a[r+1][c+1];
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			cin >> g[i][j];
			a[i][j] = 0;
			if(g[i][j] == 'S'){
				a[i][j]++;
			}
		}
	}
	for (int i = 1; i <= r; ++i){
		for (int j = 1; j <= c; ++j){
			prefix[i][j] = 	prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + a[i][j];
		}
	}
	int cnt = 0;
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			if(g[i][j] == 'M'){
				int s1 = max(1, i-d);
				int s2 = max(1, j-d);
				int e1 = min(r, i+d);
				int e2 = min(c, j+d); 
				if((prefix[e1][e2] - prefix[s1-1][e2] - prefix[e1][s2-1] + prefix[s1-1][s2-1]) >= k){
					cnt++;
				}
			}
		}
	}
	cout << cnt;
 }
 

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