제출 #335356

#제출 시각아이디문제언어결과실행 시간메모리
335356ncduy0303Collecting Mushrooms (NOI18_collectmushrooms)C++17
100 / 100
22 ms5248 KiB
#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();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...