제출 #674872

#제출 시각아이디문제언어결과실행 시간메모리
674872QwertyPiCollecting Mushrooms (NOI18_collectmushrooms)C++14
100 / 100
32 ms3152 KiB
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5e5 + 11;
char a[MAXN];
int dp[MAXN];

int r, c, d, k;
int id(int i, int j){
	return i * c + j;
}

int main(){
	cin >> r >> c >> d >> k;
	for(int i = 0; i < r; i++){
		for(int j = 0; j < c; j++){
			cin >> a[i * c + j];
		}
	}
	for(int i = 0; i < r; i++){
		for(int j = 0; j < c; j++){
			if(a[i * c + j] == 'S'){
				int r1 = max(0, i - d), r2 = min(r - 1, i + d);
				int c1 = max(0, j - d), c2 = min(c - 1, j + d);
				dp[r1 * c + c1]++;
				if(r2 != r - 1) dp[(r2 + 1) * c + c1]--;
				if(c2 != c - 1) dp[r1 * c + (c2 + 1)]--;
				if(r2 != r - 1 && c2 != c - 1) dp[(r2 + 1) * c + (c2 + 1)]++;
			}
		}
	}
	int ans = 0;
	for(int i = 0; i < r; i++){
		for(int j = 0; j < c; j++){
			if(i > 0 && j > 0) dp[i * c + j] -= dp[(i - 1) * c + j - 1];
			if(i > 0) dp[i * c + j] += dp[(i - 1) * c + j];
			if(j > 0) dp[i * c + j] += dp[i * c + j - 1];
			if(a[i * c + j] == 'M' && dp[i * c + j] >= k) ans++;
		}
	}
	cout << ans << endl;
}
#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...