Submission #1137354

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137354		mattsoh	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	0 / 100	24 ms	12416 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+1][c+1];
    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(0ll,i-d), i2 = min(i+d+1, r), j1 = max(0ll,j-d), j2 = min(c, j+d+1);
                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];
        }
    }
    ll count = 0;
    for (auto m:ms){
        if (pref[m.first][m.second] >= k) count++;
    }
    cout<<count<<endl;
}

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