Submission #1026827

---

Source Code Expand

using System;
using System.Text;
using System.Collections.Generic;
class Solve{
    public Solve(){}
    StringBuilder sb;
    public static int Main(){
        new Solve().Run();
        return 0;
    }
    void Run(){
        sb = new StringBuilder();
        Calc();
        Console.Write(sb.ToString());
    }
    void Calc(){
        string[] str = Console.ReadLine().Split(' ');
        int H = int.Parse(str[0]);
        int W = int.Parse(str[1]);
        long[,] D1 = new long[H,W];
        long[,] D2 = new long[W,H];
        for(int i=0;i<H;i++){
            str = Console.ReadLine().Split(' ');
            for(int j=0;j<W;j++){
                D1[i,j] = long.Parse(str[j]);
                D2[j,i] = long.Parse(str[j]);
            }
        }
        sb.Append(Math.Max(Calc(D1,H,W),Calc(D2,W,H))+"\n");
    }
    long Calc(long[,] m,int H,int W){
        long[,] sums = new long[H,W];
        for(int i=0;i<H;i++){
            sums[i,0] = m[i,0];
            for(int j=1;j<W;j++){
                sums[i,j] = sums[i,j-1] + m[i,j];
            }
        }
        long[] m1 = new long[H];
        for(int i=0;i<H;i++){
            m1[i] = -9000000000000;
        }
        for(int l=0;l<W;l++){
            for(int r=l;r<W;r++){
                long c1 = Math.Max(0,sums[0,r]-(l == 0 ? 0 : sums[0,l-1]));
                long c2 = Math.Max(0,sums[0,r]-(l == 0 ? 0 : sums[0,l-1]));
                long c3 = sums[0,r]-(l == 0 ? 0 : sums[0,l-1]);
                m1[0] = Math.Max(m1[0],c3);
                for(int i=1;i<H;i++){
                    c2 = Math.Max(sums[i,r]-(l == 0 ? 0 : sums[i,l-1]),c2 + sums[i,r]-(l == 0 ? 0 : sums[i,l-1]));
                    c1 = Math.Max(c1,c2);
                    c3 = Math.Max(c3,sums[i,r]-(l == 0 ? 0 : sums[i,l-1]));
                    if(c3 >= 0){
                        m1[i] = Math.Max(c1,m1[i]);
                    }
                    else{
                        m1[i] = Math.Max(c3,m1[i]);
                    }
                }
            }
        }
        long[] m2 = new long[H];
        for(int i=0;i<H;i++){
            m2[i] = -9000000000000;
        }
        for(int l=0;l<W;l++){
            for(int r=l;r<W;r++){
                long c1 = Math.Max(0,sums[H-1,r]-(l == 0 ? 0 : sums[H-1,l-1]));
                long c2 = Math.Max(0,sums[H-1,r]-(l == 0 ? 0 : sums[H-1,l-1]));
                long c3 = sums[H-1,r]-(l == 0 ? 0 : sums[H-1,l-1]);
                m2[H-1] = Math.Max(m2[H-1],c3);
                for(int i=H-2;i>=0;i--){
                    c2 = Math.Max(sums[i,r]-(l == 0 ? 0 : sums[i,l-1]),c2 + sums[i,r]-(l == 0 ? 0 : sums[i,l-1]));
                    c1 = Math.Max(c1,c2);
                    c3 = Math.Max(c3,sums[i,r]-(l == 0 ? 0 : sums[i,l-1]));
                    if(c3 >= 0){
                        m2[i] = Math.Max(c1,m2[i]);
                    }
                    else{
                        m2[i] = Math.Max(c3,m2[i]);
                    }
                }
            }
        }
        long max = -9000000000000;
        for(int i=0;i<H-1;i++){
            max = Math.Max((m1[i]+m2[i+1]),max);
        }
        return max;
    }
}

Submission Info

Judge Result