Submission #1133406

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133406		Aviansh	Collecting Mushrooms (NOI18_collectmushrooms)	C++20	100 / 100	8 ms	7916 KiB

mushrooms

#include <bits/stdc++.h>

using namespace std;

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int r,c,d,k;
    cin >> r >> c >> d >> k;
    int sprinks[r][c];
    queue<array<int,2>>mushs;
    for(int i = 0;i<r;i++){
        string s;
        cin >> s;
        for(int j = 0;j<c;j++){
            if(s[j]=='M'){
                mushs.push({i,j});
            }
            if(s[j]=='S'){
                sprinks[i][j]=1;
            }
            else{
                sprinks[i][j]=0;
            }
        }
    }
    int pref[r][c];
    pref[0][0]=sprinks[0][0];
    for(int i = 0;i<r;i++){
        for(int j = 0;j<c;j++){
            if(i==0&&j==0){
                continue;
            }
            pref[i][j]=sprinks[i][j];
            if(i){
                pref[i][j]+=pref[i-1][j];
            }
            if(j){
                pref[i][j]+=pref[i][j-1];
            }
            if(i&&j){
                pref[i][j]-=pref[i-1][j-1];
            }
        }
    }
    int ans = 0;
    while(!mushs.empty()){
        array<int,2>a=mushs.front();
        mushs.pop();
        int i1 = max(0,a[0]-d);
        int j1 = max(0,a[1]-d);
        int i2 = min(a[0]+d,r-1);
        int j2 = min(a[1]+d,c-1);
        int w = pref[i2][j2];
        if(i1){
            w-=pref[i1-1][j2];
        }
        if(j1){
            w-=pref[i2][j1-1];
        }
        if(i1&&j1){
            w+=pref[i1-1][j1-1];
        }
        if(w>=k){
            ans++;
        }
    }
    cout << ans;
    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