Submission #1357648

#TimeUsernameProblemLanguageResultExecution timeMemory
1357648jumpCollecting Mushrooms (NOI18_collectmushrooms)C++20
100 / 100
13 ms24556 KiB
#include <bits/stdc++.h>
#define int long long
int r,c,d,k;
std::vector<std::vector<int>> grid;
std::vector<std::vector<int>> dp;
std::vector<std::vector<bool>> mark;
signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cin >> r >> c >> d >> k;
  grid.resize(r+2);dp.resize(r+2);mark.resize(r+2);
  for(auto& v:grid)v.resize(c+2);
  for(auto& v:dp)v.resize(c+2);
  for(auto& v:mark)v.resize(c+2);
  for(int i=1;i<=r;i++){
    std::string in;
    std::cin >> in;
    for(int j=1;j<=c;j++){
      if(in[j-1]=='M')mark[i][j]=true;
      if(in[j-1]=='S'){
        dp[std::max((int)1,i-d)][std::max((int)1,j-d)]+=1;
        dp[std::max((int)1,i-d)][std::min(c+1,j+d+1)]-=1;
        dp[std::min(r+1,i+d+1)][std::max((int)1,j-d)]-=1;
        dp[std::min(r+1,i+d+1)][std::min(c+1,j+d+1)]+=1;
      }
    }
  }
  int cnt=0;
  for(int i=1;i<=r;i++){
    for(int j=1;j<=c;j++){
      grid[i][j]=grid[i-1][j]+grid[i][j-1]-grid[i-1][j-1]+dp[i][j];
      //std::cout << grid[i][j] << ' ';
      if(mark[i][j]&&grid[i][j]>=k)cnt+=1;
    }
    //std::cout << '\n';
  }
  std::cout << cnt;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...