Submission #1024424

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024424		thinknoexit	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	100 / 100	11 ms	9600 KiB

mushrooms

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

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m, k, d;
    cin >> n >> m >> d >> k;
    vector<vector<char>> a(n + 2, vector<char>(m + 2));
    vector<vector<int>> qs(n + 2, vector<int>(m + 2, 0));
    for (int i = 1;i <= n;i++) for (int j = 1;j <= m;j++) {
        cin >> a[i][j];
        if (a[i][j] == 'S') {
            qs[max(1, i - d)][max(1, j - d)]++;
            qs[max(1, i - d)][min(m + 1, j + d + 1)]--;
            qs[min(n + 1, i + d + 1)][max(1, j - d)]--;
            qs[min(n + 1, i + d + 1)][min(m + 1, j + d + 1)]++;
        }
    }
    int ans = 0;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            qs[i][j] += qs[i - 1][j] + qs[i][j - 1] - qs[i - 1][j - 1];
            if (a[i][j] == 'M' && qs[i][j] >= k) ans++;
        }
    }
    cout << ans;
    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