제출 #676475

#제출 시각아이디문제언어결과실행 시간메모리
676475penguin133Collecting Mushrooms (NOI18_collectmushrooms)C++17
100 / 100
38 ms9580 KiB
#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;
 }
 

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