Submission #245847

#TimeUsernameProblemLanguageResultExecution timeMemory
245847zecookiezCollecting Mushrooms (NOI18_collectmushrooms)C++17
100 / 100
23 ms21384 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 500002; vector<int> psa[MAXN]; int main() { cin.sync_with_stdio(0); cin.tie(0); cout.tie(0); int r, c, d, k; cin >> r >> c >> d >> k; vector<pair<int, int>> mush; psa[0].resize(c + 1, 0); for(int i = 1; i <= r; ++i){ string s; cin >> s; psa[i].resize(c + 1, 0); for(int j = 1; j <= c; ++j){ if(s[j - 1] == 'M') mush.emplace_back(i, j); else if(s[j - 1] == 'S') { psa[i][j] = 1; } psa[i][j] += psa[i][j - 1] + psa[i - 1][j] - psa[i - 1][j - 1]; } } int cnt = 0; for(auto i : mush){ int lx = max(1, i.first - d), rx = min(r, i.first + d); int ly = max(1, i.second - d), ry = min(c, i.second + d); int tot = psa[rx][ry] - psa[rx][ly - 1] - psa[lx - 1][ry] + psa[lx - 1][ly - 1]; if(tot >= k) ++cnt; } cout << cnt << "\n"; return 0; }
#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...