제출 #1338307

#제출 시각아이디문제언어결과실행 시간메모리
1338307mantaggezCollecting Mushrooms (NOI18_collectmushrooms)C++20
100 / 100
12 ms9560 KiB
#include <bits/stdc++.h>

using namespace std;

int r, c, d, k;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> r >> c >> d >> k;
    vector<vector<char>> grid(r + 2, vector<char> (c + 2));
    vector<vector<int>> qs(r + 2, vector<int> (c + 2, 0));
    for(int i=1;i<=r;i++) {
        for(int j=1;j<=c;j++) {
            cin >> grid[i][j];
            if(grid[i][j] == 'S') {
                qs[max(1, i - d)][max(1, j - d)]++;
                qs[min(r + 1, i + d + 1)][min(c + 1, j + d + 1)]++;
                qs[max(1, i - d)][min(c + 1, j + d + 1)]--;
                qs[min(r + 1, i + d + 1)][max(1, j - d)]--;
                // for(int i=1;i<=r;i++) {
                //     for(int j=1;j<=c;j++) {
                //         cout << qs[i][j] << ' ';
                //     }
                //     cout << '\n';
                // }
                // cout << '\n';
            }
        }
    }

    
    
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++)
            qs[i][j] += (qs[i - 1][j] + qs[i][j - 1] - qs[i - 1][j - 1]);
    
    // for(int i=1;i<=r;i++) {
    //     for(int j=1;j<=c;j++) {
    //         cout << qs[i][j] << ' ';
    //     }
    //     cout << '\n';
    // }

    int ans = 0;
    for(int i=1;i<=r;i++) {
        for(int j=1;j<=c;j++) {
            if(grid[i][j] == 'M' && qs[i][j] >= 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...