Submission #1239092

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239092		caterpillow	Collecting Mushrooms (NOI18_collectmushrooms)	C++20	100 / 100	15 ms	10404 KiB

mushrooms

#include <bits/stdc++.h>

using namespace std;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    
    int rs, cs, d, k;
    cin >> rs >> cs >> d >> k;
    vector<vector<int>> pfx(rs + 1, vector<int>(cs + 1));
    vector<pair<int, int>> mushrooms;
    for (int r = 0; r < rs; r++) {
        for (int c = 0; c < cs; c++) {
            char ch;
            cin >> ch;
            if (ch == 'S') pfx[r + 1][c + 1]++;
            if (ch == 'M') mushrooms.push_back({r, c});
        }
    }
    for (int r = 0; r <= rs; r++) {
        for (int c = 0; c < cs; c++) {
            pfx[r][c + 1] += pfx[r][c];
        } 
    }
    for (int r = 0; r < rs; r++) {
        for (int c = 0; c <= cs; c++) {
            pfx[r + 1][c] += pfx[r][c];
        } 
    }
    int ans = 0;
    for (auto [r, c] : mushrooms) {
        int r1 = max(0, r - d);
        int c1 = max(0, c - d);
        int r2 = min(rs, r + d + 1);
        int c2 = min(cs, c + d + 1);
        if (pfx[r2][c2] - pfx[r1][c2] - pfx[r2][c1] + pfx[r1][c1] >= k) ans++;
    }
    cout << ans << '\n';
}

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