Submission #798721

#	Time	Username	Problem	Language	Result	Execution time	Memory
798721		devariaota	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	100 / 100	27 ms	21824 KiB

mushrooms

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

int main(){
  int r, c, d, k, count = 0;
  int x1, x2, x3, x4, y1, y2, y3, y4, xs, ys;
  string s;
  vector<string> grid;
  
  vector<vector<int>> sumgrid;
  vector<int> temp;
  
  vector<pair<int,int>> mushroom, sprinkler;
  cin >> r >> c >> d >> k;
  
  
  for(int i = 0; i <= r+4; i++){
    temp.clear();
    for(int j = 0; j <= c+4; j++){
      temp.push_back(0);
    }
    sumgrid.push_back(temp);
  }
  for(int i = 0; i < r; i++){
    cin >> s;
    grid.push_back(s);
    for(int j = 0; j < c; j++){
      if(s[j] == 'M'){
        mushroom.push_back({i+1, j+1});
      }
      else if(s[j] == 'S'){
        sprinkler.push_back({i+1, j+1});
      }
      
    }
  }
  for(auto coor : sprinkler){
    xs = coor.first;
    ys = coor.second;
    
    x1 = xs-d; 
    y1 = ys-d;
    
    x2 = xs+d+1;
    y2 = ys-d;
    
    x3 = xs-d;
    y3 = ys+d+1;
    
    x4 = xs+d+1;
    y4 = ys+d+1;
    
    if(x1 < 1) x1 = 1;
    if(y1 < 1) y1 = 1;
    
    if(x2 > r+1) x2 = r+1;
    if(y2 < 1) y2 = 1;
    
    if(x3 < 1) x3 = 1;
    if(y3 > c+1) y3 = c+1;
    
    if(x4 > r+1) x4 = r+1;
    if(y4 > c+1) y4 = c+1;  
    
    
    sumgrid[x1][y1] += 1;
    sumgrid[x2][y2] -= 1;
    sumgrid[x3][y3] -= 1;
    sumgrid[x4][y4] += 1; 
  }
  
  // for(int i = 0; i <= r+1; i++){
    // for(int j = 0; j <= c+1; j++){
      // cout << sumgrid[i][j];
    // }
    // cout << endl;
  // }

  for(int i = 0; i<= r+1; i++){
    for(int j = 1; j <= c+1; j++){
      sumgrid[i][j] += sumgrid[i][j-1];
    }
  }
  
  for(int i = 1; i<= r+1; i++){
    for(int j = 0; j <= c+1; j++){
      sumgrid[i][j] += sumgrid[i-1][j];
    }
  }
  
  for(auto coor : mushroom){
    xs = coor.first;
    ys = coor.second;
    
    if(sumgrid[xs][ys] >= k){
      count++;
    }
  }
  
  // cout << endl;
  // for(int i = 0; i <= r+1; i++){
    // for(int j = 0; j <= c+1; j++){
      // cout << sumgrid[i][j];
    // }
    // cout << endl;
  // }
  cout << count;
}

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