Submission #1206359

#TimeUsernameProblemLanguageResultExecution timeMemory
1206359loomCollecting Mushrooms (NOI18_collectmushrooms)C++20
100 / 100
16 ms16560 KiB
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 5e18
#define nl '\n'

inline void solve(){
   int n, m, d, k;
   cin>>n>>m>>d>>k;

   int pre[n+1][m+1];
   for(int i=0; i<n; i++) pre[i][0] = 0;
   for(int i=0; i<m; i++) pre[0][i] = 0;

   vector<pair<int,int>> v;
   for(int i=1; i<=n; i++){
      for(int j=1; j<=m; j++){
         char c;
         cin>>c;
         pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + (c == 'S');
         if(c == 'M') v.push_back({i, j});
      }
   }

   int ans = 0;
   for(auto [i, j] : v){
      int a = max(i-d, 1ll), b = max(j-d, 1ll), x = min(i+d, n), y = min(j+d, m);
      ans += pre[x][y] - pre[x][b-1] - pre[a-1][y] + pre[a-1][b-1] >= k;
   }

   cout<<ans;
}

signed main(){
   ios_base::sync_with_stdio(0);
   cin.tie(NULL);cout.tie(NULL);

   int t = 1;
   //cin>>t;
   while(t--) solve();

   return 0;
}
#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...