K-Triangles

시간 제한3초메모리 제한512 MB

요약
n×m 정수 행렬과 k가 주어질 때, 서로 겹치지 않는 두 k-삼각형(맨해튼 거리 k 미만의 네 방향 쐐기)을 골라 원소 합의 최댓값을 구한다.
난이도

어려움10점 중 8점

유형
누적 합, 동적 계획법, 행렬, 구현
정답자
아직 제출이 없습니다

문제

You are given an \(n \times m\) matrix \(A\) with integer elements and a positive integer \(k\).

For a given cell \((x_0, y_0)\) of matrix \(A\), we define the following sets of cells as \(k\)-triangles with center \((x_0, y_0)\):

  • \(T_0 = {(x, y) : x \ge x_0, y \ge y_0, |x − x_0| + |y − y_0| < k}\) if \(1 \le x_0 \le n − k + 1, 1 \le y_0 \le m − k + 1\);
  • \(T_1 = {(x, y) : x \le x_0, y \ge y_0, |x − x_0| + |y − y_0| < k}\) if \(k \le x_0 \le n, 1 \le y_0 \le m − k + 1\);
  • \(T_2 = {(x, y) : x \le x_0, y \le y_0, |x − x_0| + |y − y_0| < k}\) if \(k \le x_0 \le n, k \le y_0 \le m\);
  • \(T_3 = {(x, y) : x \ge x_0, y \le y_0, |x − x_0| + |y − y_0| < k}\) if \(1 \le x_0 \le n − k + 1, k \le y_0 \le m\).

For a given \(k\)-triangle \(T\), we define its cost \(f(T) = \sum_{(x,y) \in T}{A_{x,y}}\).

Your task is to find the maximum possible total cost of any two non-intersecting \(k\)-triangles. Formally, you have to find \(\max_{P \cup Q = \emptyset}{f(P) + f(Q)}\) where \(P\) and \(Q\) are some \(k\)-triangles.

입력

The first line contains three space-separated integers \(n\), \(m\), \(k\) (\(1 \le n, m, k \le 1500\)).

Each of the next \(n\) lines contains \(m\) space-separated integers; the \(i\)-th line contains integers \(A_{i,1}, A_{i,2}, \dots , A_{i,m}\) (\(−10^9 \le A_{i,j} \le 10^9\)).

It is guaranteed that there is at least one way to choose two non-intersecting \(k\)-triangles in the matrix.

출력

Print a single integer: the maximum possible sum of costs of two non-intersecting \(k\)-triangles.

힌트

In the second example, the answer is made up of two k-triangles of type \(T_1\) with centers at \((4, 1)\) and \((3, 3)\).

예제2

  1. 예제 1

    입력
    3 4 2
0 1 0 0
0 1 1 1
0 0 1 1
    예상 출력
    6

  2. 예제 2

    입력
    4 5 3
-5 -7 4 5 -3
-7 -5 8 0 -7
4 6 2 6 5
7 3 1 -7 7
    예상 출력
    39