Submission #534848

#TimeUsernameProblemLanguageResultExecution timeMemory
534848makanhuliaCollecting Mushrooms (NOI18_collectmushrooms)C++17
100 / 100
19 ms8900 KiB
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll mod = 1e9 + 7;
#pragma GCC optimize("Ofast")
#define vi vector<int>
#define vll vector<ll>
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fi first
#define sc second
#define endl '\n'
#define gl ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int r, c, d, k;
char x;

int main()
{
  gl
  cin >> r >> c >> d >> k;
  int grid[r + 1][c + 1];
  memset(grid, 0, sizeof(grid));
  vector<pii > v;
  
  for(int i = 1; i <= r; i++){
    for(int j = 1; j <= c; j++){
      cin >> x;
      if(x == 'M')
        v.pb({i, j});
      if(x == 'S')
        grid[i][j]++;
    }
  }
  
  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];
    }
  }
  
  int ans = 0;
  for(auto i : v){
    int x = i.fi, y = i.sc;
    pii L = make_pair(max(1, x - d), max(1, y - d));
    pii R = make_pair(min(x + d, r), min(y + d, c));
    ans += (grid[R.fi][R.sc] - grid[R.fi][L.sc - 1] - grid[L.fi - 1][R.sc] + grid[L.fi-1][L.sc-1] >= k);
  }
  
  cout << ans << endl;
}
#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...