제출 #1307792

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1307792		lyra_g13	Collecting Mushrooms (NOI18_collectmushrooms)	C++20	79 / 100	2097 ms	39472 KiB

mushrooms

#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));

  if (r == 1) {
    vector<ll> count(c + 1), pref(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);

      count[topl]++;
      count[topr + 1]--;
    }

    pref[0] = count[0];
    for (int i = 1; i < c; i++) {
      pref[i] = pref[i - 1] + count[i];
    }

    ll ans = 0;
    for (auto [x, y] : m) {
      if (pref[y] >= k) {
        ans++;
      }
    }
    cout << ans << "\n";

  } else {
    vector<vector<ll>> count(r, vector<ll>(c));
    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++) {
        for (int j = topl; j <= topr; j++) {
          count[i][j]++;
        }
      }
    }

    ll ans = 0;
    for (auto [x, y] : m) {
      if (count[x][y] >= k) {
        ans++;
      }
    }

    cout << ans << "\n";
  }
}

• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 18 / 18
• Subtask 4: 23 / 23
• Subtask 5: 19 / 19
• Subtask 6: 0 / 21