Submission #1238235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238235		caterpillow	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	100 / 100	10 ms	6748 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<char>> grid(rs, vector<char>(cs));
    vector<vector<int>> pfx(rs + 1, vector<int>(cs + 1));
    for (int r = 0; r < rs; r++) {
        for (int c = 0; c < cs; c++) {
            cin >> grid[r][c];
            if (grid[r][c] == 'S') {
                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);
                pfx[r1][c1]++;
                pfx[r1][c2]--;
                pfx[r2][c1]--;
                pfx[r2][c2]++;
            }
        }
    }
    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 (int r = 0; r < rs; r++) for (int c = 0; c < cs; c++) if (pfx[r][c] >= k && grid[r][c] == 'M') 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