This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<iostream>
#include<cassert>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
#include<set>
#include<queue>
#include<map>
using namespace std;
const int N = (int)4e5 + 7;
const int inf = (int)1e9 + 7;
const int MOD = (int)998244353;
const long long INF = (long long)1e18 + 7;
int mult(int x, int y) {
return 1ll*x*y%MOD;
}
int sum(int x, int y) {
x += y;
if(x >= MOD) {
x -= MOD;
}
return x;
}
int sub(int x, int y) {
x -= y;
if(x < 0) {
x += MOD;
}
return x;
}
int n, m, d, k;
int main() {
ios_base::sync_with_stdio(NULL);
cin.tie(0);
cin >> n >> m >> d >> k;
char a[n+1][m+1];
int b[n+5][m+5];
memset(b, 0, sizeof(b));
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
cin >> a[i][j];
}
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
if(a[i][j] == 'S') {
int x1 = max(1, i-d);
int y1 = max(1, j-d);
int x2 = min(n, i+d);
int y2 = min(m, j+d);
b[x1][y1]++;
b[x1][y2+1]--;
b[x2+1][y1]--;
b[x2+1][y2+1]++;
}
}
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
b[i][j]+=b[i-1][j];
b[i][j]+=b[i][j-1];
b[i][j]-=b[i-1][j-1];
}
}
int ans = 0;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
ans += (a[i][j] == 'M' && b[i][j] >= k);
}
}
cout << ans;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |