Submission #163208

#	Time	Username	Problem	Language	Result	Execution time	Memory
163208		aggu_01000101	Collecting Mushrooms (NOI18_collectmushrooms)	C++14	100 / 100	52 ms	5752 KiB

mushrooms

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

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