Submission #618491

---

Source Code Expand

using System;
using System.Collections.Generic;
using System.Linq;

class Program {
    static string ReadLine() { return Console.ReadLine(); }
    static int ReadInt() { return int.Parse(ReadLine()); }
    static int[] ReadInts() { return ReadLine().Split().Select(int.Parse).ToArray(); }
    static string[] ReadStrings() { return ReadLine().Split(); }

    static int[,] Rotate(int[,] g) {
        int rows = g.GetLength(0);
        int cols = g.GetLength(1);
        var t = new int[cols, rows];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                t[j, rows-i-1] = g[i, j];
            }
        }
        return t;
    }

    static long Calc(int[,] g) {
        int rows = g.GetLength(0);
        int cols = g.GetLength(1);

        // 縦方向の和を求める
        var sum = new long[rows, cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                sum[i, j] = g[i, j];
                if (i > 0) sum[i, j] += sum[i-1, j];
            }
        }

        // row i から row j までの範囲に対して、部分列の最大和を求める
        var maxRow = new long[rows, rows]; // maxRow[i, j] 行 i から行 j までの範囲の矩形の最大和
        for (int i = 0; i < rows; i++)
            for (int j = 0; j < rows; j++)
                maxRow[i, j] = long.MinValue;

        var dp = new long[cols];
        for (int i = 0; i < rows; i++) {
            for (int j = i; j < rows; j++) {
                long max = long.MinValue;
                for (int k = 0; k < cols; k++) {
                    long x = sum[j, k] - (i > 0 ? sum[i-1, k] : 0);

                    if (k == 0) dp[k] = x;
                    else dp[k] = Math.Max(dp[k-1] + x, x);

                    max = Math.Max(max, dp[k]);
                }
                maxRow[i, j] = max;
            }
        }

        // 領域を二つに分割して、それぞれ最大和を求める
        long ans = long.MinValue;
        for (int i = 0; i < rows-1; i++) { // i までが top の領域
            long topMax = long.MinValue;
            long btmMax = long.MinValue;
            for (int j = 0; j < rows; j++) { // 行 j から行 k までの矩形
                for (int k = j; k < rows; k++) {
                    if (k <= i) topMax = Math.Max(topMax, maxRow[j, k]);
                    else if (j > i) btmMax = Math.Max(btmMax, maxRow[j, k]);
                }
            }

            ans = Math.Max(ans, topMax + btmMax);
        }
        return ans;
    }

    static void Main() {
        var hw = ReadInts();
        int rows = hw[0], cols = hw[1];

        var g = new int[rows, cols];
        for (int i = 0; i < rows; i++) {
            var xs = ReadInts();
            for (int j = 0; j < cols; j++) {
                g[i, j] = xs[j];
            }
        }

        var ans = Math.Max(Calc(g), Calc(Rotate(g)));
        Console.WriteLine(ans);
    }
}

Submission Info

Judge Result