Submission #1016302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016302		toast12	Collecting Mushrooms (NOI18_collectmushrooms)	C++14	100 / 100	24 ms	14776 KiB

mushrooms

#include <bits/stdc++.h>
using namespace std;

int main() {
    int r, c, d, k;
    cin >> r >> c >> d >> k;
    vector<vector<int>> ps(r+2, vector<int>(c+2));
    vector<pair<int, int>> mushrooms;
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            char x;
            cin >> x;
            if (x == 'S')
                ps[i][j]++;
            else if (x == 'M')
                mushrooms.push_back({i, j});
        }
    }
    for (int j = 1; j <= c; j++) {
        for (int i = 1; i <= r; i++) {
            ps[i][j+1] += ps[i][j];
            ps[i][j] += ps[i-1][j];
        }
    }
    int ans = 0;
    for (auto m : mushrooms) {
        int row = m.first, col = m.second;
        int left = max(1, col-d);
        int right = min(c, col+d);
        int up = max(1, row-d);
        int down = min(r, row+d);
        int cnt = ps[down][right]-ps[up-1][right]-ps[down][left-1]+ps[up-1][left-1];
        if (cnt >= k)
            ans++;
    }
    cout << ans << '\n';
    return 0;
}

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