Submission #1309784

#TimeUsernameProblemLanguageResultExecution timeMemory
1309784ladnooooCollecting Mushrooms (NOI18_collectmushrooms)C++20
100 / 100
12 ms13124 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back

const int maxN = 2e5 + 7;

void solve() {
    int n, m, d, k;
    cin >> n >> m >> d >> k;

    char a[n + 1][m + 1];
    
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) cin >> a[i][j];
    }

    vector<vector<int>> pref(n + 1, vector<int>(m + 1, 0));

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            pref[i][j] = (a[i][j] == 'S') + pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
        }
    }

    auto get = [&](int x1, int y1, int x2, int y2) {
        int pr = pref[x2][y2];
        pr -= pref[x1 - 1][y2];
        pr -= pref[x2][y1 - 1];
        pr += pref[x1 - 1][y1 - 1];
        return pr;
    };

    int ans = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(a[i][j] == 'M') {
                int x1 = max(1LL, i - d);
                int y1 = max(1LL, j - d);
                int x2 = min(n, i + d);
                int y2 = min(m, j + d);
                int cnt = get(x1, y1, x2, y2);
                if(cnt >= k) ans++;
            }
        }
    }
    cout << ans << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("input.txt", "r", stdin);
    int t = 1;
    //cin >> t;
    while(t--) solve();
}
#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...