oj.uz

Submission #798703

# Submission time Handle Problem Language Result Execution time Memory
798703 2023-07-31T01:14:39 Z kebine Collecting Mushrooms (NOI18_collectmushrooms) C++17
9 / 100
 30 ms 32660 KB 
#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<pair<int,int>> mushroom, sprinkler;
  cin >> r >> c >> d >> k;
  
  int sumgrid[r+5][c+5];
  
  for(int i = 0; i <= r+3; i++){
    for(int j = 0; j <= c+3; j++){
      sumgrid[i][j] = 0;
    }
  }
  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) y2 = 1;
    if(y3 > c+1) y3 = c+1;
    
    if(x4 > r+1) x4 = r+1;
    if(x4 > c+1) x4 = 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 = 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 << count;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 296 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 372 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 304 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 296 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 372 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Incorrect 1 ms 212 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 1620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 30 ms 32660 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 296 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 372 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Incorrect 1 ms 212 KB Output isn't correct
11 Halted 0 ms 0 KB -