Submission #1164243

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164243		ChottuF	Collecting Mushrooms (NOI18_collectmushrooms)	C++20	100 / 100	47 ms	12636 KiB

mushrooms

#include<bits/stdc++.h>
using namespace std;

#define int long long

signed main(){
    int n,m,x,y;
    cin >> n >> m >> x >> y;
    vector<vector<char>> v(n,vector<char>(m));
    for (int i=0; i<n; i++){
        for (int j=0; j<m; j++) cin>>v[i][j];
    }
    
    vector<vector<int>> frq(n+1,vector<int>(m+1));
    for (int i=0; i<n; i++){
        for (int j=0; j<m; j++){
            if (v[i][j]=='.' or v[i][j]=='M')continue;
            if (n<m){
                for (int k=max(0LL,i-x); k<=min(n-1,i+x); k++){
                    frq[k][max(j-x,0LL)]++;
                    frq[k][min(j+x+1,m)]--;
                }
            }
            else{
                for (int k=max(0ll,j-x); k<=min(m-1,j+x); k++){
                    frq[max(i-x,0ll)][k]++;
                    frq[min(i+x+1,n)][k]--;
                }
            }
        }
    }
    if (n<m){
        for (int i=0; i<n; i++){
            for (int j=1; j<m; j++)
                frq[i][j]+=frq[i][j-1];
        }
    }
    else{
        for (int i=1; i<n; i++){
            for (int j=0; j<m; j++)
                frq[i][j]+=frq[i-1][j];
        }
    }
    int ans=0;
    for (int i=0; i<n; i++){
        for (int j=0; j<m; j++){
            if (v[i][j]=='M' && frq[i][j]>=y) ans++;
        }
    }
    cout<< ans << '\n';
    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