Submission #853219

#TimeUsernameProblemLanguageResultExecution timeMemory
853219annabeth9680Collecting Mushrooms (NOI18_collectmushrooms)C++17
100 / 100
22 ms3376 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 5e5 + 11; char a[MAXN]; int dp[MAXN]; int r, c, d, k; int id(int i, int j){ return i * c + j; } int main(){ cin >> r >> c >> d >> k; for(int i = 0; i < r; i++){ for(int j = 0; j < c; j++){ cin >> a[i * c + j]; } } for(int i = 0; i < r; i++){ for(int j = 0; j < c; j++){ if(a[i * c + j] == 'S'){ int r1 = max(0, i - d), r2 = min(r - 1, i + d); int c1 = max(0, j - d), c2 = min(c - 1, j + d); dp[r1 * c + c1]++; if(r2 != r - 1) dp[(r2 + 1) * c + c1]--; if(c2 != c - 1) dp[r1 * c + (c2 + 1)]--; if(r2 != r - 1 && c2 != c - 1) dp[(r2 + 1) * c + (c2 + 1)]++; } } } int ans = 0; for(int i = 0; i < r; i++){ for(int j = 0; j < c; j++){ if(i > 0 && j > 0) dp[i * c + j] -= dp[(i - 1) * c + j - 1]; if(i > 0) dp[i * c + j] += dp[(i - 1) * c + j]; if(j > 0) dp[i * c + j] += dp[i * c + j - 1]; if(a[i * c + j] == 'M' && dp[i * c + j] >= k) ans++; } } cout << ans << endl; 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...