Submission #534848

#	Time	Username	Problem	Language	Result	Execution time	Memory
534848		makanhulia	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	100 / 100	19 ms	8900 KiB

mushrooms

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll mod = 1e9 + 7;
#pragma GCC optimize("Ofast")
#define vi vector<int>
#define vll vector<ll>
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fi first
#define sc second
#define endl '\n'
#define gl ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int r, c, d, k;
char x;

int main()
{
  gl
  cin >> r >> c >> d >> k;
  int grid[r + 1][c + 1];
  memset(grid, 0, sizeof(grid));
  vector<pii > v;
  
  for(int i = 1; i <= r; i++){
    for(int j = 1; j <= c; j++){
      cin >> x;
      if(x == 'M')
        v.pb({i, j});
      if(x == 'S')
        grid[i][j]++;
    }
  }
  
  for(int i = 1; i <= r; i++){
    for(int j = 1; j <= c; j++){
      grid[i][j] += grid[i - 1][j] + grid[i][j - 1] - grid[i - 1][j - 1];
    }
  }
  
  int ans = 0;
  for(auto i : v){
    int x = i.fi, y = i.sc;
    pii L = make_pair(max(1, x - d), max(1, y - d));
    pii R = make_pair(min(x + d, r), min(y + d, c));
    ans += (grid[R.fi][R.sc] - grid[R.fi][L.sc - 1] - grid[L.fi - 1][R.sc] + grid[L.fi-1][L.sc-1] >= k);
  }
  
  cout << ans << endl;
}

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