Submission #689761

#	Time	Username	Problem	Language	Result	Execution time	Memory
689761		zeroesandones	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	100 / 100	19 ms	16968 KiB

mushrooms

#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<ll, ll> pi;

#define FOR(i, j, k) for (ll i = j; i < (ll) k; ++i)
#define FORD(i, j, k) for (ll i = j; i >= (ll) k; --i)
#define nl "\n"
#define sp " "

#define all(x) (x).begin(), (x).end()
#define sc second
#define fr first
#define pb push_back

void solve()
{
    ll n, m, d, k;
    cin >> n >> m >> d >> k;

    vector<pi> mush;
    ll sum[n + 1][m + 1] = {};

    FOR(i, 1, n + 1) {
        FOR(j, 1, m + 1) {
            char c;
            cin >> c;
            ll cost = 0;
            if(c == 'S')
                cost = 1;
            else if(c == 'M')
                mush.pb({i, j});
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + cost;
        }
    }

    ll ans = 0;
    for(auto [x, y] : mush) {
        ll leftN = max(1LL, x - d);
        ll rightN = min(x + d, n);
        ll leftM = max(1LL, y - d);
        ll rightM = min(y + d, m);

        ll curr = sum[rightN][rightM] - sum[leftN - 1][rightM] - sum[rightN][leftM - 1] + sum[leftN - 1][leftM - 1];
        if(curr >= k)
            ++ans;
    }

    cout << ans << nl;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
}

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