Submission #1113674

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113674		vjudge1	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	100 / 100	31 ms	27896 KiB

mushrooms

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

#define i128 __int128
#define ll long long
#define ff first
#define ss second
#define pll pair<ll, ll>
#define pb push_back
#define elif else if

#define fast_io ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

const ll MOD = 1e9+7;
const ll base = 1e18;
const ll maxn = 5e5+5;


int main(){
    fast_io;
    ll r,c,d,k;
    cin>>r>>c>>d>>k;
    vector<vector<ll>> prefix(r + 5,vector<ll>(c + 5, 0));
    vector<vector<char>> a(r + 5, vector<char> (c + 5));
    for (int i=0;i<r;i++){
        for (int j=0;j<c;j++){
            cin>>a[i][j];
            //cout<<a[0][i]<<endl;
            if (a[i][j]=='S'){
                //range
                ll startR=max(0LL,i-d);
                ll startC=max(0LL,j-d);
                ll endR=min(r-1,i+d);
                ll endC=min(c-1,j+d);
                prefix[startR][startC]+=1;
                prefix[startR][endC+1]-=1;
                prefix[endR+1][startC]-=1;
                prefix[endR+1][endC+1]+=1;

            }
        }   
    }
    //cout << 0<<endl; 
    for (int i=0;i<r;i++){
        for (int j=0;j<c;j++){

            prefix[i][j]=(i == 0 ? 0 : prefix[i-1][j])+(j == 0 ? 0 : prefix[i][j-1])-(i == 0 || j == 0 ? 0 : prefix[i-1][j-1]) +prefix[i][j];
        }  
    }
    ll ans=0;
    for (int i=0;i<r;i++){
        for (int j=0;j<c;j++){
            if (a[i][j]=='M'&&prefix[i][j]>=k){
                ans++;
            }
            //cout<<p[i]<<endl;
        }
    }
    cout<<ans<<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