Submission #970318

#	Time	Username	Problem	Language	Result	Execution time	Memory
970318		VMaksimoski008	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	100 / 100	25 ms	7772 KiB

mushrooms

#include <bits/stdc++.h>

#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
//#define int long long

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;
const double eps = 1e-9;

int32_t main() {
    int n, m, d, k;
    cin >> n >> m >> d >> k;

    char mat[n+1][m+1];
    int pref[n+2][m+2];
    memset(pref, 0, sizeof(pref));

    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            cin >> mat[i][j];
            if(mat[i][j] == 'S') {
                int x1 = max(1, i - d);
                int x2 = min(n, i + d);
                int y1 = max(1, j - d);
                int y2 = min(m, j + d);
                pref[x1][y1]++; pref[x2+1][y2+1]++;
                pref[x1][y2+1]--, pref[x2+1][y1]--;
            }
        }
    }

    int ans = 0;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            pref[i][j] += pref[i-1][j] + pref[i][j-1];
            pref[i][j] -= pref[i-1][j-1];
            if(pref[i][j] >= k && mat[i][j] == 'M') ans++;
        }
    }

    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