제출 #1311138

#제출 시각아이디문제언어결과실행 시간메모리
1311138aryanCollecting Mushrooms (NOI18_collectmushrooms)C++20
100 / 100
13 ms11208 KiB
#include<bits/stdc++.h>
using namespace std;

using i64 = long long;


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

    int n,m,d,k;
    cin >> n >> m >> d >> k;
    vector<vector<char>> c(n + 1,vector<char>(m + 1));
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            cin >> c[i][j];
        }
    }
    vector<vector<int>> a(n + 1,vector<int>(m + 1));
    vector<vector<int>> pref(n + 1, vector<int>(m + 1));
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            if(c[i][j] == 'S'){
                a[i][j] = 1;
            }
        }
    } 


    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            pref[i][j] = a[i][j] + pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
        }
    }

    /*
        1 2 3 4 5
        6 7 8 9 1
        1 2 3 4 5
        1 2 3 4 5
    */

    int ans = 0;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            if(c[i][j] != 'M') continue;
            int x1 = max(1,i - d);
            int x2 = min(n,i + d);
            int y1 = max(1,j - d);
            int y2 = min(m,j + d);

            int tot =  pref[x2][y2] - pref[x1 - 1][y2] - pref[x2][y1 - 1] + pref[x1 - 1][y1 - 1];
            if(tot >= k){
                ans ++;
            }
        }
    }
    cout << ans << '\n';

    return 0;
}
#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...