Submission #1332009

#TimeUsernameProblemLanguageResultExecution timeMemory
1332009uranhishigCollecting Mushrooms (NOI18_collectmushrooms)C++20
0 / 100
28 ms12796 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long


signed main(){
    int r, c, d, k;
    cin >> r >> c >> d >> k;
    char ch[r][c];
    int p[r + 1][c + 1] ={0};
    vector<pair<int, int>> muug;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> ch[i][j];
            if(ch[i][j] == 'M') {
                muug.push_back({i, j});
            }
            else if(ch[i][j] == 'S') {
                p[i + 1][j + 1] = 1;
            }
        }
    }
    for (int i = 1; i < r; i++) {
        for (int j = 1; j < c; j++) {
            p[i][j] += p[i - 1][j] + p[i][j- 1] - p[i - 1][j - 1];
        }
    }
    int ans = 0;
    for(pair<int, int> pr : muug){
        int x=pr.first, y=pr.second;
        int x1 = max(0LL, x - d) + 1;
        int y1 = max(0LL, y - d) + 1;
        int x2 = min(r - 1, x + d) + 1;
        int y2 = min(c - 1, y + d) + 1;
        int cnt = p[x2][y2] - p[x1-1][y2] - p[x2][y1-1] + p[x1-1][y1-1];
        if (cnt >= k) ans++;
    }
    cout << ans;
}
#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...