Submission #1006026

#TimeUsernameProblemLanguageResultExecution timeMemory
1006026kebineCollecting Mushrooms (NOI18_collectmushrooms)C++17
100 / 100
49 ms48744 KiB
#include <bits/stdc++.h>
using namespace std;
#define pii pair<ll,ll>
#define REP(i,x,y) for(ll i=x;i<=y;i++)
#define freeopen   freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
#define mod 1000000000
#define pb push_back
#define mk make_pair
#define ll long long
#define foor(x,vec) for(auto x:vec ){cout<<x<<" ";}
#define fi first
#define se second
#define MAXN 200069
#define lld long double
#define cha ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ffl fflush(stdout)
#define sst string
ll mvx[]={0,0,-1,1};
ll mvy[]={1,-1,0,0};

map<sst,ll> cnt;
ll n,m,s,d;
void solve(){
    cin>>n>>m>>d>>s;
    char c[n+10][m+10];
    ll dp[n+10][m+10];
    REP(i,0,n+3){
        REP(j,0,m+3)dp[i][j]=0;
    }
    REP(i,1,n)REP(j,1,m)cin>>c[i][j];
    REP(i,1,n){
        REP(j,1,m){
            if(c[i][j]=='S'){
                dp[min(i+d,n)+1][min(j+d,m)+1]++;
                dp[max(i-d,(ll)1)][max(j-d,(ll)1)]++;
                dp[max(i-d,(ll)1)][min(j+d,m)+1]--;
                dp[min(i+d,n)+1][max(j-d,(ll)1)]--;
            }
        }
    }
    ll ans=0;
    REP(i,1,n){
        REP(j,1,m){
            dp[i][j]+=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];
            if(dp[i][j]>=s && c[i][j]=='M')ans++;
        }
    }
    cout<<ans<<endl;
}

int main(){
    ll tc;
    tc=1;
//    cin>>tc;
    while(tc--){
        solve();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...