Submission #668242

#TimeUsernameProblemLanguageResultExecution timeMemory
668242600MihneaCollecting Mushrooms (NOI18_collectmushrooms)C++17
60 / 100
2065 ms3804 KiB
#include <bits/stdc++.h> using namespace std; int main() { #ifdef ONPC freopen ("input.txt", "r", stdin); #endif // ONPC #ifndef ONPC ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #endif // ONPC int n, m, r, need; cin >> n >> m >> r >> need; vector<pair<int, int>> mus, spr; for (int i = 0; i < n; i++) { string s; cin >> s; assert((int) s.size() == m); for (int j = 0; j < m; j++) { char ch = s[j]; if (ch == '.') { continue; } if (ch == 'S') { spr.push_back({i, j}); continue; } if (ch == 'M') { mus.push_back({i, j}); continue; } assert(0); } } int sol = 0; sort(mus.begin(), mus.end()); sort(spr.begin(), spr.end()); int p1 = 0, p2 = 0; for (auto &it : mus) { while (p1 < (int) spr.size() && spr[p1].first <= it.first + r) { p1++; } while (p2 < (int) spr.size() && spr[p2].first < it.first - r) { p2++; } int cnt = 0; for (int j = p2; j < p1; j++) { int d = max(abs(spr[j].first - it.first), abs(spr[j].second - it.second)); if (d <= r) { cnt++; } } sol += (cnt >= need); } cout << sol << "\n"; }
#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...