记录编号	79634	评测结果	AAAAAAAAAA
题目名称	[NOIP 2008]传纸条	最终得分	100
用户昵称	Ezoi_XY	是否通过	通过
代码语言	Pascal	运行时间	0.017 s
提交时间	2013-11-06 07:24:48	内存使用	1.46 MiB

Program cog219;
    Var
        F:Array[0..105,0..55,0..55]Of Longint;
        A:Array[0..105,0..55]Of Longint;
        I,J,K,T,L,N,M:Longint;
    Function Min(A,B:Longint):Longint;
        Begin
            If A<B Then Exit(A);
            Exit(B);
        End;
    Function Max(A,B:Longint):Longint;
        Begin
            If A>B Then Exit(A);
            Exit(B);
        End;
    Begin
        Assign(Input,'message.in');
        Assign(Output,'message.out');
        Reset(Input);
        Rewrite(Output);
        Fillchar(F,Sizeof(F),$FF);
        Fillchar(A,Sizeof(A),0);
        F[1,1,1]:=0;
        Read(M,N);
        For I:=1 To M Do
            For J:=1 To N Do
                Read(A[I+J-1,Min(J,M-I+1)]);
        F[2,1,2]:=A[2,1]+A[2,2];
        For I:=3 To N+M-2 Do
            Begin
                If I<Min(N,M) Then T:=I
                Else If I>Max(N,M) Then T:=N+M-I
                Else T:=Min(N,M);
                For J:=1 To T-1 Do
                    For K:=J+1 To T Do
                        Begin
                            F[I,J,K]:=A[I,J]+A[I,K];
                            L:=F[I-1,J,K];
                            If (T=I) Or (N<M) And (I<=Max(N,M))
                                Then L:=Max(Max(L,F[I-1,J-1,K-1]),Max(F[I-1,J,K-1],F[I-1,J-1,K]))
                                Else L:=Max(Max(L,F[I-1,J+1,K+1]),Max(F[I-1,J,K+1],F[I-1,J+1,K]));
                            Inc(F[I,J,K],L);
                        End;
            End;
        Writeln(F[N+M-2,1,2]);
        Close(Input);
        Close(Output);
    End.