제출 #1006030

#제출 시각아이디문제언어결과실행 시간메모리
1006030kebineCollecting Mushrooms (NOI18_collectmushrooms)C++17
100 / 100
18 ms24556 KiB
#include<bits/stdc++.h> #define int long long #define str string using namespace std; bool debug = 0; int R, C, D, S; // for R = 1, we can use a sliding window method or pref sum // similarly, the full solution uses a 2d pref sum? signed main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> R >> C >> D >> S; str grid[R+1]; int pref[R+5][C+5]; for (int i=0; i<R; i++) { cin >> grid[i]; } for (int i=0; i<=R+1; i++) { for (int j=0; j<=C+1; j++) { pref[i][j] = 0; } } for (int i=1; i<=R; i++) { for (int j=1; j<=C; j++) { pref[i][j] = pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1]; if (grid[i-1][j-1] == 'S') pref[i][j]++; } } int ans = 0; for (int i=1; i<=R; i++) { for (int j=1; j<=C; j++) { if (grid[i-1][j-1] == 'M') { int r1 = max(1ll, i-D), c1 = max(1ll, j-D), r2 = min(R, i+D), c2 = min(C, j+D); int sprinkle = pref[r2][c2] - pref[r1-1][c2] - pref[r2][c1-1] + pref[r1-1][c1-1]; if (debug) { cout << "i: " << i << " j: " << j << " " << r1 << " " << c1 << " to " << r2 << " " << c2 << " has " << sprinkle << " sprinklers" << endl; } if (sprinkle >= S) { 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...