제출 #1308357

#제출 시각아이디문제언어결과실행 시간메모리
1308357athenaCollecting Mushrooms (NOI18_collectmushrooms)C++20
100 / 100
99 ms39380 KiB
#include <bits/stdc++.h> using ll = long long; using namespace std; int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); ll r, c, d, k; cin >> r >> c >> d >> k; ll realr = r; ll realc = c; if (r > c) { std::swap(r, c); } set<pair<ll, ll>> s, m; vector<vector<char>> adj(r, vector<char>(c)); vector<vector<ll>> count(r, vector<ll>(c + 1)), pref(r, vector<ll>(c + 1)); if (realr != r) { for (int i = 0; i < realr; i++) { for (int j = 0; j < realc; j++) { cin >> adj[j][i]; if (adj[j][i] == 'S') { s.insert({j, i}); } if (adj[j][i] == 'M') { m.insert({j, i}); } } } } else { for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { cin >> adj[i][j]; if (adj[i][j] == 'S') { s.insert({i, j}); } if (adj[i][j] == 'M') { m.insert({i, j}); } } } } for (auto [x, y] : s) { ll topl = max(0LL, y - d); ll topr = min((c - 1), y + d); ll downl = max(0LL, x - d); ll downr = min((r - 1), x + d); for (int i = downl; i <= downr; i++) { count[i][topl]++; count[i][topr + 1]--; } } for (int i = 0; i < r; i++) { pref[i][0] = count[i][0]; for (int j = 1; j < c; j++) { pref[i][j] = pref[i][j - 1] + count[i][j]; } } ll ans = 0; for (auto [x, y] : m) { if (pref[x][y] >= k) { ans++; } } cout << ans << "\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...