Submission #1006053

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006053		christinelynn	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	100 / 100	17 ms	30832 KiB

mushrooms

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;

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

  int r, c, d, s;
  cin >> r >> c >> d >> s;
  vector<vector<char>> a(r + 5, vector<char>(c + 5));
  for (int i = 1; i <= r; ++i) {
    for (int j = 1; j <= c; ++j) {
      cin >> a[i][j];
    }
  }

  vector<vector<int>> pre(r + 5, vector<int>(c + 5));
  for (int i = 1; i <= r; ++i) {
    for (int j = 1; j <= c; ++j) {
      pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1];
      if (a[i][j] == 'S') {
        ++pre[i][j];
      }
    }
  }

  auto f = [&](int lx, int ly, int rx, int ry) -> int {
    return pre[rx][ry] - pre[rx][ly - 1] - pre[lx - 1][ry] + pre[lx - 1][ly - 1];
  };

  int ans = 0;
  for (int i = 1; i <= r; ++i) {
    for (int j = 1; j <= c; ++j) {
      if (a[i][j] == 'M' && f(max(i - d, 1LL), max(j - d, 1LL), min(i + d, r), min(j + d, c)) >= s) {
        ++ans;
      }
    }
  }

  cout << ans << '\n';

  return 0;
}

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