제출 #1311138

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1311138		aryan	Collecting Mushrooms (NOI18_collectmushrooms)	C++20	100 / 100	13 ms	11208 KiB

mushrooms

#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;
}

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