제출 #163208

#제출 시각아이디문제언어결과실행 시간메모리
163208aggu_01000101Collecting Mushrooms (NOI18_collectmushrooms)C++14
100 / 100
52 ms5752 KiB
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <vector>
#define double long double
using namespace std;
int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int r, c, d, k;
    cin>>r>>c>>d>>k;
    int arr[r+1][c+1];
    bool mush[r+1][c+1];
    for(int i = 0;i<=r;i++){
        for(int j = 0;j<=c;j++){
            arr[i][j] = 0;
            mush[i][j] = false;
        }
    }
    for(int i = 0;i<r;i++){
        for(int j = 0;j<c;j++){
            char s;
            cin>>s;
            if(s=='M') mush[i][j] = true;
            else if(s=='S'){
                int bottom = max(0, i-d);
                int left = max(0, j-d);
                int right = min(c-1, j+d);
                int top = min(r-1, i+d);
                //cout<<"("<<i<<", "<<j<<") "<<bottom<<left<<right<<top<<endl;
                arr[bottom][left]++;
                arr[bottom][right+1]--;
                arr[top+1][left]--;
                arr[top+1][right+1]++;
            }
        }
    }

    for(int i = 1;i<=r;i++){
        arr[i][0]+=arr[i-1][0];
    }
    for(int i = 1;i<=c;i++){
        arr[0][i]+=arr[0][i-1];
    }
    for(int i = 1;i<=r;i++){
        for(int j = 1;j<=c;j++){
            arr[i][j]-=arr[i-1][j-1];
            arr[i][j]+=arr[i-1][j];
            arr[i][j]+=arr[i][j-1];
        }
    }
    int cnt = 0;
    for(int i = 0;i<r;i++){
        for(int j = 0;j<c;j++){
            if(arr[i][j]>=k && mush[i][j]) cnt++;
        }
    }
    cout<<cnt<<endl;
}
#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...