Submission #1087865

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087865		whtth	Collecting Mushrooms (NOI18_collectmushrooms)	C++14	100 / 100	25 ms	23084 KiB

mushrooms

#include<bits/stdc++.h>
using namespace std;
int n, m, d, k, ans=0;
string S[500010];
vector<vector<int>> s;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("collect.inp", "r", stdin);
    //freopen("collect.out", "w", stdout);
    cin>>n>>m>>d>>k;
    for(int i=0;i<n;i++){
        cin>>S[i];
    }
    for(int i=0;i<=n;i++){
        vector<int> row;
        for(int j=0;j<=m;j++)row.push_back(0);
        s.push_back(row);
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            s[i+1][j+1]=s[i+1][j]+s[i][j+1]-s[i][j];
            if(S[i][j]=='S')s[i+1][j+1]++;
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(S[i][j]=='M'){
                int o1=i+d, o2=i-d, o3=j-d, o4=j+d;
                int l=max(0, o3);
                int r=min(m-1, o4);
                int d=max(0, o2);
                int u=min(o1, n-1);
                if(s[u+1][r+1]-s[u+1][l]-s[d][r+1]+s[d][l]>=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