Submission #1005991

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005991		kebine	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	18 / 100	42 ms	48732 KiB

mushrooms

#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>>s>>d;
    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){
            dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];
            if(c[i][j]=='S'){
                dp[i][j]++;
            }
        }
    }
    ll ans=0;
    REP(i,1,n){
        REP(j,1,m){
            if(c[i][j]=='M'){
                ll take=dp[min(i+d,n)][min(j+d,m)]-dp[max(i-d-1,(ll)0)][min(j+d,m)]-dp[min(i+d,n)][max(j-d-1,(ll)0)]+dp[max(i-d-1,(ll)0)][max(j-d-1,(ll)0)];
                if(take>=s){
                    ans++;
                }
            }
        }
    }
    cout<<ans<<endl;
}

int main(){
    ll tc;
    tc=1;
//    cin>>tc;
    while(tc--){
        solve();
    }
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 10
• Subtask 3: 18 / 18
• Subtask 4: 0 / 23
• Subtask 5: 0 / 19
• Subtask 6: 0 / 21