Submission #534655

#	Time	Username	Problem	Language	Result	Execution time	Memory
534655		kebine	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	100 / 100	18 ms	10436 KiB

mushrooms

#include <bits/stdc++.h>

using namespace std;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int r, c, d, k;
    cin >> r >> c >> d >> k;

    int ans = 0;
    int prefix[r + 2][c + 2];
    vector<pair<int, int>>v;
    memset(prefix, 0, sizeof(prefix));

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

    for(auto &[x, y]: v){
        int TLX = max(1, (x - d));
        int TLY = max(1, (y - d));
        int BRX = min(r, (x + d));
        int BRY = min(c, (y + d));

        int tmp = prefix[BRX][BRY] - prefix[BRX][TLY - 1] - prefix[TLX - 1][BRY] + prefix[TLX - 1][TLY - 1];

        ans += (tmp >= k);
    }

    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