Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của ladpro98

program KVIP;
uses    math;
const   maxn=1111;
        fi='';
var     c:array[1..maxn,1..maxn] of longint;
        f:array[1..maxn] of int64;
        n,i,j:longint;
        inp:text;
        res:int64;
begin
        assign(inp,fi);reset(inp);
        readln(inp,n);
        for i:=1 to n do
        for j:=1 to n do begin
                read(inp,c[i,j]);
                if i=j then inc(res,c[i,j]);
        end;
        for i:=2 to n do f[i]:=low(int64);
        for i:=1 to n do begin
                for j:=i to n do
                f[j]:=max(f[j],f[i]+c[i,j]-c[i,i]);
                f[1]:=max(f[1],f[i]+c[i,1]-c[i,i]);
        end;
        write(res+f[1]);
end.