Submission #1332415

#	Time	Username	Problem	Language	Result	Execution time	Memory
1332415		kantaponz	Collecting Mushrooms (NOI18_collectmushrooms)	C++20	100 / 100	16 ms	16384 KiB

mushrooms

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

#define ll long long


int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int r, c, d, k;
    cin >> r >> c >> d >> k;
    vector<pair<int,int>> qrs;
    int a[r + 5][c + 5];
    memset(a, 0, sizeof a);

    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            char x;
            cin >> x;
            if (x == 'M') {
                qrs.emplace_back(i, j);
            }
            if (x == 'S') {
                a[i][j]++;
            }
        }
    }

    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            a[i][j] += a[i-1][j] + a[i][j-1] - a[i-1][j-1];
        }
    }

    int ans = 0;
    for (auto [i, j] : qrs) {
        int x1, y1, x2, y2;
        x1 = max(i - d, 1);
        y1 = max(j - d, 1);
        x2 = min(i + d, r);
        y2 = min(j + d, c);
        if (a[x2][y2] - a[x1 - 1][y2] - a[x2][y1 - 1] + a[x1 - 1][y1 - 1] >= k) {
            ans++;
        }
    }


    cout << ans;
}

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