십자가 부분합

문제 설명

이차원 정수 배열 numbers와 구간 합 쿼리 queries가 주어질 때, 각 쿼리 [cx, cy, s]에 대해 중심의 좌표가 (cx, cy)이고 크기가 s인 십자가 영역 내의 모든 원소의 합을 반환하는 solution 함수를 작성하시오.

십자가 영역은 중심 (cx, cy)에서부터 상, 하, 좌, 우로 각각 s칸 만큼 뻗어나간 영역을 의미합니다. 해당 영역의 모양을 도식화하면 아래와 같습니다.

(크기가 0인 경우)

      *    

(크기가 1인 경우)

      * 
     ***    
      *

(크기가 2인 경우)

      * 
      *     
    *****
      *   
      * 

제한 사항

• numbers는 NxM 크기의 직사각형 행렬 모양입니다.
  • N(=numbers의 행 개수)은 1 이상 1,000 이하의 자연수입니다.
  • M(=numbers의 열 개수)은 1 이상 1,000 이하의 자연수입니다.
• numbers의 각 원소는 -1,000 이상 1,000 이하의 정수입니다.
• queries의 길이는 1 이상 50,000 이하입니다.
• queries의 각 원소는 [cx, cy, s]로 이루어져 있습니다.
  • 1 ≤ cx ≤ N(=numbers의 행 개수)
  • 1 ≤ cy ≤ M(=numbers의 열 개수)
  • 모든 질의 [cx, cy, s]에 해당하는 십자가 영역은 항상 행렬 내에만 존재합니다.

예시 테스트케이스 설명

1번 테스트케이스 설명

• 첫 번째 쿼리: [2,2,1]

    2
  4 5 6
    8
  

  • 2+4+5+6+8 = 25
• 두 번째 쿼리: [3,3,0]
  • 중심 (3,3) 하나만 포함
  • 9 = 9

2번 테스트케이스 설명

• 첫 번째 쿼리: [2,3,1]

    4
  9 2 6
    5
  

  • 4+9+2+6+5 = 26
• 두 번째 쿼리: [1,4,0]
  • 중심 (1,4) 하나만 포함
  • 1 = 1

3번 테스트케이스 설명

• 첫 번째 쿼리: [3,3,2]

      3
      8
  13 14 15
     18
     23
  

  • 3+8+13+14+15+18+23+12+17+22 = 117
• 두 번째 쿼리: [3,3,1]

      8
  12 13 14
     18
  

  • 8+12+13+14+18 = 65
• 세 번째 쿼리: [3,3,0]
  • 중심 (3,3) 하나만 포함
  • 13 = 13