Submission #1264406

#TimeUsernameProblemLanguageResultExecution timeMemory
1264406sohamsen15Collecting Mushrooms (NOI18_collectmushrooms)C++20
100 / 100
19 ms19876 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int r, c, d, k; cin >> r >> c >> d >> k; vector<vector<int>> a(r + 1, vector<int>(c + 1, 0)), b(r + 1, vector<int>(c + 1, 0)); for (int i = 1; i <= r; i++) for (int j = 1; j <= c; j++) { char c; cin >> c; if (c == 'M') a[i][j] = 1; if (c == 'S') b[i][j] = 1; } vector<vector<int>> p(r + 1, vector<int>(c + 1, 0)); for (int i = 1; i <= r; i++) for (int j = 1; j <= c; j++) p[i][j] = b[i][j] + p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1]; function<int(int, int, int, int)> f = [&](int i, int j, int k, int l) { k = min(k, r), l = min(l, c), i = max(1, i), j = max(1, j); return p[k][l] - p[k][j - 1] - p[i - 1][l] + p[i - 1][j - 1]; }; vector<vector<int>> ans(r + 1, vector<int>(c + 1, 0)); for (int i = 1; i <= r; i++) for (int j = 1; j <= c; j++) if (a[i][j] == 1) if (f(i - d, j - d, i + d, j + d) >= k) ans[i][j] = 1; int ret = 0; for (int i = 1; i <= r; i++) for (int j = 1; j <= c; j++) ret += ans[i][j]; cout << ret; }
#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...