Submission #1314668

#TimeUsernameProblemLanguageResultExecution timeMemory
1314668joshjuiceCollecting Mushrooms (NOI18_collectmushrooms)C++20
100 / 100
14 ms6732 KiB
#include <bits/stdc++.h>
using namespace std;

int main() {
  int r, c, d, k; cin >> r >> c >> d >> k;
  vector<vector<char>> grid(r, vector<char> (c));
  vector<vector<int>> ps(r+1, vector<int> (c+1));
  for (int i = 0; i < r; ++i) {
    string s; cin >> s;
    for (int j = 0; j < c; ++j) {
      grid[i][j] = s[j];
      ps[i+1][j+1] = (grid[i][j] == 'S' ? 1 : 0);
    }
  }
  for (int i = 1; i <= r; ++i) {
    for (int j = 1; j <= c; ++j) {
      ps[i][j] += ps[i][j-1]+ps[i-1][j]-ps[i-1][j-1];
    }
  }
  int a = 0;
  for (int i = 0; i < r; ++i) {
    for (int j = 0; j < c; ++j) {
      if (grid[i][j] == 'M') {
        int x1 = max(0, i-d);
        int x2 = min(r-1, i+d);
        int y1 = max(0, j-d);
        int y2 = min(c-1, j+d);
        int sum = ps[x2+1][y2+1]+ps[x1][y1]-ps[x1][y2+1]-ps[x2+1][y1];
        if (sum >= k) a++;
      }
    }
  }
  cout << a;
}
#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...