제출 #1006011

#제출 시각아이디문제언어결과실행 시간메모리
1006011devariaotaCollecting Mushrooms (NOI18_collectmushrooms)C++17
0 / 100
18 ms24552 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+1; i++) { for (int j=1; j<=C+1; j++) { pref[i][j] = pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1]; if (i <= R && j <= C && 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(0ll, i-D), c1 = max(0ll, j-D), r2 = min(R+1, i+D), c2 = min(C+1, j+D); int sprinkle = pref[r2][c2] - pref[r1-1][c2] - pref[r2][c1-1] + pref[r1-1][c1-1]; if (sprinkle >= S) { if (debug) { cout << i << " " << j << " is good" << endl; cout << "since " << r1 << " " << c1 << " to " << r2 << " " << c2 << " has " << sprinkle << " sprinklers" << endl; } 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...