Submission #1309784

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309784		ladnoooo	Collecting Mushrooms (NOI18_collectmushrooms)	C++20	100 / 100	12 ms	13124 KiB

mushrooms

#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();
}

• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 18 / 18
• Subtask 4: 23 / 23
• Subtask 5: 19 / 19
• Subtask 6: 21 / 21