18579번 - K-Triangles 다국어

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)\).