Submission #1307793

#TimeUsernameProblemLanguageResultExecution timeMemory
1307793lyra_g13Collecting Mushrooms (NOI18_collectmushrooms)C++20
79 / 100
2095 ms39400 KiB
#include <bits/stdc++.h>
using ll = long long;
using namespace std;

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  ll r, c, d, k;
  cin >> r >> c >> d >> k;
  set<pair<ll, ll>> s, m;
  vector<vector<char>> adj(r, vector<char>(c));
  vector<vector<ll>> count(r, vector<ll>(c + 1)), pref(r, vector<ll>(c + 1));
  for (int i = 0; i < r; i++) {
    for (int j = 0; j < c; j++) {
      cin >> adj[i][j];
      if (adj[i][j] == 'S') {
        s.insert({i, j});
      }
      if (adj[i][j] == 'M') {
        m.insert({i, j});
      }
    }
  }
  for (auto [x, y] : s) {

    ll topl = max(0LL, y - d);
    ll topr = min((c - 1), y + d);
    ll downl = max(0LL, x - d);
    ll downr = min((r - 1), x + d);

    for (int i = downl; i <= downr; i++) {
      count[i][topl]++;
      count[i][topr + 1]--;
    }
  }

  for (int i = 0; i < r; i++) {
    pref[i][0] = count[i][0];
    for (int j = 1; j < c; j++) {
      pref[i][j] = pref[i][j - 1] + count[i][j];
    }
  }
  ll ans = 0;
  for (auto [x, y] : m) {
    if (pref[x][y] >= k) {
      ans++;
    }
  }

  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...