시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 74 | 24 | 6 | 15.385% |
$K \times N$ 격자 그래프 $A$가 주어진다. 격자 그래프는 노드가 직사각형 모양으로 배치되어 있는 그래프이며, 각 노드는 위, 아래, 왼쪽, 그리고 오른쪽 노드와 연결되어 있다.
위에서 $x$번째 줄 왼쪽에서 $y$번째 칸의 노드를 $A_{xy}$로 나타내자. 이 때, 다음 쿼리를 수행하는 프로그램을 작성하시오.
1 x1 y1 x2 y2
: $x_1 \le x \le x_2$, $y_1 \le y \le y_2$인 $A_{xy}$만으로 이루어진 크기 $1$ 이상의 연결 요소 중, 구성 노드의 값의 합이 가장 큰 연결 요소를 찾아 그 합을 출력한다.2 x y v
: $A_{xy}$의 값을 $v$로 설정한다.첫 번째 줄에 격자 그래프의 크기를 나타내는 정수 $K$, $N$이 주어진다. ($K \in \left\{1,2,3\right\}$, $1 \le N \le 100\,000$)
두 번째 줄부터 $K$개의 줄에 걸쳐 격자 그래프의 노드의 값들이 주어진다. ($-10^9 \le A_{ij} \le 10^9$)
다음 줄에는 쿼리의 개수 $Q$가 주어진다. ($1 \le Q \le 100\,000$)
다음 줄부터 $Q$개의 쿼리가 문제에서 언급한 형식으로 한 줄에 하나씩 주어진다.
입력으로 들어오는 모든 수는 정수다.
각각의 쿼리마다 정답을 한 줄에 하나씩 출력한다.
3 8 -1 5 6 3 -1 7 -6 9 6 8 -9 2 -4 5 1 8 3 4 1 5 -7 -3 2 7 4 1 1 2 3 7 2 1 5 -100 1 1 2 3 7 1 2 2 2 4
48 45 8
University > 서강대학교 > 2021 Sogang Programming Contest > Champion H번
University > 서강대학교 > 2021 Sogang Programming Contest > Open P번