Submission #1006030

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006030		kebine	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	100 / 100	18 ms	24556 KiB

mushrooms

#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";
}

• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 18 / 18
• Subtask 4: 23 / 23
• Subtask 5: 19 / 19
• Subtask 6: 21 / 21