Submission #1271313

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271313		zulmuw	Collecting Mushrooms (NOI18_collectmushrooms)	C++20	100 / 100	24 ms	36924 KiB

mushrooms

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

#define int long long 

int r, c, d, k;
vector<pair<int,int>> vm, vs;
vector<vector<int>> ps;

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);

  cin >> r >> c >> d >> k;
  ps.assign(r+5, vector<int> (c+5, 0));
  
  for (int i=0; i<r; ++i) {
    string s; cin >> s;
    for (int j=0; j<c; ++j) {
      if (s[j] == 'S') {
        vs.push_back({i, j});
      }
      if (s[j] == 'M') {
        vm.push_back({i, j});
      }
    }
  }
  
  for (auto [a, b] : vs) {
    int ul1 = max(0LL, a-d), ul2 = max(0LL, b-d); 
    int dr1 = min(r, a+d), dr2 = min(c, b+d);
    // cout << a << " " << b << "\n";
    // cout << " -> " << ul1 << " " << ul2 << " "<< dr1 << " "<< dr2 << "\n";
    
    ps[ul1][ul2]++;
    ps[dr1+1][ul2]--;
    ps[ul1][dr2+1]--;
    ps[dr1+1][dr2+1]++;

  //   for (int i = 0; i < r; ++i) {
  //     for (int j = 0; j < c; ++j) {
  //       cout << ps[i][j] << " ";
  //     }
  //     cout << "\n";
  //   }

  // cout << "\n\n";
  }
  
  for (int i=1; i<r; ++i) {
    for (int j=0; j<c; ++j) {
      ps[i][j] += ps[i-1][j];
    }
  }
  
  for (int i=0; i<r; ++i) {
    for (int j=1; j<c; ++j) {
      ps[i][j] += ps[i][j-1];
    }
  }
  
  int ans = 0;
  for (auto [a, b]: vm) {
    if (ps[a][b] >= k) ans++; 
  }
  cout << ans;
}

  

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