제출 #1333205

#제출 시각아이디문제언어결과실행 시간메모리
1333205michael12Collecting Mushrooms (NOI18_collectmushrooms)C++20
100 / 100
12 ms12632 KiB
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<string>
#include<stack>
#include<queue>
#include<array>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define endl '\n'
#define int long long
using namespace std;
const int maxn = 1e6 + 10;
const int oo = 1e18;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int r, c, d, k;
    cin >> r >> c >> d >> k;
    vector<vector<char>> T(r, vector<char>(c));
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            cin >> T[i][j];
        }
    }
    vector<vector<int>> p(r + 1, vector<int>(c + 1));
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            if(T[i][j] == 'S'){
               int x = max(0LL, i - d);
               int y = max(0LL, j - d);
               int x1 = min(r, i + d + 1);
               int y1 = min(c, j + d + 1);
               p[x][y] += 1;
               p[x1][y] += -1;
               p[x][y1] += -1;
               p[x1][y1] += 1;
            }
        }
    }
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            if(i > 0){
                p[i][j] += p[i - 1][j];
            }
            if(j > 0){
                p[i][j] += p[i][j - 1];
            }
            if(i > 0 && j > 0){
                p[i][j] -= p[i - 1][j - 1];
            }
        }
    }
    int ans = 0;
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            if(p[i][j] >= k && T[i][j] == 'M'){
               ans += 1;
            }
        }
    }
    cout << ans;

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