Submission #1006016

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006016		devariaota	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	0 / 100	29 ms	40172 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[C+1];
  int pref[C+5][R+5]; 
  for (int i=0; i<C; i++) {
    cin >> grid[i];
  }
  for (int i=0; i<=C+1; i++) {
    for (int j=0; j<=R+1; j++) {
      pref[i][j] = 0;
    }
  }
  for (int i=1; i<=C+1; i++) {
    for (int j=1; j<=R+1; j++) {
      pref[i][j] = pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1];
      if (i <= C && j <= R && grid[i-1][j-1] == 'S') pref[i][j]++;
    }
  }
  int ans = 0;
  for (int i=1; i<=C; i++) {
    for (int j=1; j<=R; j++) {
      if (grid[i-1][j-1] == 'M') {
        int r1 = max(0ll, i-D), c1 = max(0ll, j-D), r2 = min(C+1, i+D), c2 = min(R+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";
}

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