제출 #533750

#제출 시각아이디문제언어결과실행 시간메모리
533750kebineCollecting Mushrooms (NOI18_collectmushrooms)C++17
100 / 100
19 ms10408 KiB
#include <bits/stdc++.h>
using namespace std;

int n, m, d, k;
pair<int,int> g(pair<int,int> a, int d){
  int x = a.first, y = a.second;
  x = max(1, min(x+d, n));
  y = max(1, min(y+d, m));
  return {x, y};
}

int main(){
  cin.tie(0) -> ios_base::sync_with_stdio(0);

  cin >> n >> m >> d >> k;
  vector<vector<int>> ps(n + 1, vector<int>(m + 1));
  vector<pair<int,int>> v;
  for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++){
      char a;
      cin >> a;
      if(a == 'M')
      {
        v.push_back({i, j});
      }
      else if(a == 'S')
      {
        ps[i][j]++;
      }
    }
  for(int i=1;i<=n;i++)
  {
    for(int j=1;j<=m;j++)
    {
      ps[i][j] += ps[i-1][j] + ps[i][j-1] - ps[i-1][j-1];
    }
  }
  int ans = 0;
  for(auto i : v){
    auto se = g(i, d);
    auto fi = g(i, -d);
    ans += ((long long)ps[se.first][se.second] - ps[se.first][fi.second-1] - ps[fi.first-1][se.second] + ps[fi.first-1][fi.second-1]) >= k;
  }  
  cout << ans << '\n';
}
#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...