Submission #1015461

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015461		overwatch9	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	100 / 100	14 ms	7312 KiB

mushrooms

#include <bits/stdc++.h>
using namespace std;
int main() {
    int r, c, d, k;
    cin >> r >> c >> d >> k;
    vector <string> grid(r+1);
    for (int i = 1; i <= r; i++) {
        cin >> grid[i];
        grid[i] = "0" + grid[i];
    }
    vector <vector <int>> pfx(r+1, vector <int> (c+1));
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            pfx[i][j] = pfx[i-1][j] + pfx[i][j-1] - pfx[i-1][j-1];
            if (grid[i][j] == 'S')
                pfx[i][j]++;
        }
    }
    int ans = 0;
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            if (grid[i][j] != 'M')
                continue;
            // cout << pfx[min(r, i + d)][min(j + d, c)] << '\n';
            // cout << pfx[max(0, i - d - 1)][min(j + d, c)] << '\n';
            // cout << pfx[min(r, i + d)][min(0, j - d - 1)] << '\n';
            int sum = pfx[min(r, i + d)][min(j + d, c)] - pfx[max(0, i - d - 1)][min(j + d, c)] - pfx[min(r, i + d)][max(0, j - d - 1)] + pfx[max(0, i - d - 1)][max(0, j - d - 1)];
            if (sum >= 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