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 <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 11;
char grid[MAXN];
int dp[MAXN];
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int R,C,D,K; cin >> R >> C >> D >> K;
for(int i = 0;i<R;++i){
for(int j = 0;j<C;++j){
cin >> grid[i*C+j];
if(grid[i*C+j] == 'S'){
int minr = max(i-D,0), maxr = min(i+D,R-1), minc = max(j-D,0), maxc = min(j+D,C-1);
dp[minr*C+minc]++;
if(maxr != R-1) dp[(maxr+1)*C+minc]--;
if(maxc != C-1) dp[minr*C+maxc+1]--;
if(maxr != R-1 && maxc != C-1) dp[(maxr+1)*C+maxc+1]++;
}
}
}
int ans = 0;
for(int i = 0;i<R;++i){
for(int j = 0;j<C;++j){
if(i) dp[i*C+j] += dp[(i-1)*C+j];
if(j) dp[i*C+j] += dp[i*C+j-1];
if(i > 0 && j > 0) dp[i*C+j] -= dp[(i-1)*C+j-1];
if(dp[i*C+j] >= K && grid[i*C+j] == 'M'){
//cout << i << " " << j << "\n";
ans++;
}
}
}
cout << ans << endl;
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... |