Submission #245847

#	Time	Username	Problem	Language	Result	Execution time	Memory
245847		zecookiez	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	100 / 100	23 ms	21384 KiB

mushrooms

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500002;
vector<int> psa[MAXN];
int main() {
    cin.sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int r, c, d, k; cin >> r >> c >> d >> k;
    vector<pair<int, int>> mush;
    psa[0].resize(c + 1, 0);
    for(int i = 1; i <= r; ++i){
        string s; cin >> s;
        psa[i].resize(c + 1, 0);
        for(int j = 1; j <= c; ++j){
            if(s[j - 1] == 'M') mush.emplace_back(i, j);
            else if(s[j - 1] == 'S') {
                psa[i][j] = 1;
            }
            psa[i][j] += psa[i][j - 1] + psa[i - 1][j] - psa[i - 1][j - 1];
        }
    }
    int cnt = 0;
    for(auto i : mush){
        int lx = max(1, i.first - d),  rx = min(r, i.first + d);
        int ly = max(1, i.second - d), ry = min(c, i.second + d);
        int tot = psa[rx][ry] - psa[rx][ly - 1] - psa[lx - 1][ry] + psa[lx - 1][ly - 1];
        if(tot >= k) ++cnt;
    }
    cout << cnt << "\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