Submission #1137356

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137356		mattsoh	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	100 / 100	44 ms	51624 KiB

mushrooms

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxr = 1e5 + 10;
signed main(){
    ll r,c,d,k;cin>>r>>c>>d>>k;
    vector<pair<ll,ll>> ms;
    ll pref[r+10][c+10];
    for (ll i = 0;i<=r;i++){
        for (ll j = 0;j<=c;j++){
            pref[i][j] = 0;
        }
    }
    for (ll i = 1;i<=r;i++){
        for (ll j = 1;j<=c;j++){
            char x;cin>>x;
            if (x == 'M') ms.push_back({i,j});
            else if (x == 'S') {
                ll i1 = max(1ll,i-d), i2 = min(i+d+1, r+1), j1 = max(1ll,j-d), j2 = min(c+1, j+d+1);
                // cout<<i1<<i2<<j1<<j2<<endl;
                pref[i1][j1]++;
                pref[i1][j2]--;
                pref[i2][j1]--;
                pref[i2][j2]++;
            }
        }
    }
    for (ll i = 1;i<=r;i++){
        for (ll j = 1;j<=c;j++){
            pref[i][j] += pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1];
            // cout<<pref[i][j]<<' ';
        }
        // cout<<endl;
    }
    ll count = 0;
    for (auto m:ms){
        if (pref[m.first][m.second] >= k) count++;
    }
    cout<<count<<endl;
}

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