Submission #799864

#	Time	Username	Problem	Language	Result	Execution time	Memory
799864		christinelynn	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	100 / 100	42 ms	52152 KiB

mushrooms

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define pll pair<ll, ll>
using namespace std;

int main(){
  ll r, c, d, k;
  cin >> r >> c >> d >> k;
  ll pref[r+10][c+10];
  memset(pref, 0, sizeof(pref));
  vector<pll>mushroom;
  for(int i=1; i<=r; i++){
    for(int j=1; j<=c; j++){
      char g; cin >> g;
      if(g=='M') mushroom.pb({i, j});
      pref[i][j]=pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1]+(g=='S');
    }
  }
  ll ans=0;
  for(auto i : mushroom){
    ll a, b, x, y;
//    cout << i.fi << " " << i.se << endl;
    a=max(1ll, i.fi-d);
    b=max(1ll, i.se-d);
    x=min(r, i.fi+d);
    y=min(c, i.se+d);
//    cout << a << b << " " << x << y << endl;
    ll tot = pref[x][y]-pref[a-1][y]-pref[x][b-1]+pref[a-1][b-1];
    if(tot>=k) ans++;
  }
  cout << ans << endl;
  return 0;
}

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