Submission #335356

#	Time	Username	Problem	Language	Result	Execution time	Memory
335356		ncduy0303	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	100 / 100	22 ms	5248 KiB

mushrooms

#include <bits/stdc++.h>

using namespace std;

#define ar array
#define ll long long

const int MAX_N = 1e5 + 1;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll LINF = 1e18;



void solve() {
    int r, c, d, k; cin >> r >> c >> d >> k;
    int ps[r + 1][c + 1] = {}; 
    char grid[r + 1][c + 1];
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            cin >> grid[i][j];
            ps[i][j] = (grid[i][j] == 'S') + ps[i - 1][j] + ps[i][j - 1] - ps[i - 1][j - 1];
        }
    }
    int ans = 0;
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            if (grid[i][j] == 'M') {
                int tli = max(1, i - d), tlj = max(1, j - d);
                int bri = min(r, i + d), brj = min(c, j + d);
                int cnt = ps[bri][brj] + ps[tli - 1][tlj - 1] - ps[tli - 1][brj] - ps[bri][tlj - 1];
                ans += (cnt >= k);
            }
        }
    }
    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    int tc = 1;
    // cin >> tc;
    for (int t = 1; t <= tc; t++) {
        // cout << "Case #" << 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