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 flashmt

#include<iostream>
#include<algorithm>
#define oo -10000000
#define fr(a,b,c) for (a=b;a<=c;a++)
using namespace std;

int m,n,a[22][22],b[22][22],f[22][22][22][22],res;

int main()
{
    int i,j,u,v,x,y,p,q,t,s;
    cin >> m >> n;
    fr(i,0,21)
     fr(j,0,21)
      fr(u,0,21)
       fr(v,0,21)
        f[i][j][u][v]=oo;
    fr(i,1,m)
      fr(j,1,n)
      {
         cin >> x;
         a[i][j]=a[i][j-1]+x;
         b[i][j]=b[i-1][j]+x;
         f[i][j][i][j]=x;
      }
    fr(i,1,m)
      fr(j,1,n-1)
        fr(u,j+1,n)
          f[i][j][i][u]=max(f[i][j][i][u-1],a[i][u]-a[i][j-1]);
    fr(i,1,n)
      fr(j,1,m-1)
        fr(u,j+1,m)
          f[j][i][u][i]=max(f[j][i][u-1][i],b[u][i]-b[j-1][i]);
    fr(x,2,m)
     fr(y,2,n)
      fr(i,1,m-x+1)
       fr(j,1,n-y+1)
       {
         u=i+x-1; 
         v=j+y-1;
         t=f[i][j][i][v];
         s=a[i][v]-a[i][j-1];
         t=max(t,s+f[i+1][v][u][v]);
         s+=b[u][v]-b[i][v];
         for (q=v-1;q>=j;q--)
         {
            s+=a[u][v-1]-a[u][q-1];
            t=max(t,s); 
            for (p=u-1;p>i;p--)
            {
                s+=b[u-1][q]-b[p-1][q];
                t=max(t,s);
                if (q<v-1) t=max(t,s+f[p][q+1][u-1][v-1]); 
                s-=b[u-1][q]-b[p-1][q];               
            }
            s-=a[u][v-1]-a[u][q-1];      
         }         
         f[i][j][u][v]=t;
         if (i>1 || j>1)
         {
            t=max(f[i][j][u-1][v],f[i][j][u][v-1]);
            f[i][j][u][v]=max(f[i][j][u][v],t);
         }
       }
    res=a[1][1]-a[1][0];
    fr(i,1,m)
      fr(j,1,n)
        res=max(res,f[1][1][i][j]); 
    cout << res << endl;
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>
const int N = 21;
using namespace std;
int m, n, a[N][N];
int F[N][N][N][N][4];
bool was[N][N][N][N][4];

int DP(int i, int j, int lx, int ly, int dir) {
    int &ans = F[i][j][lx][ly][dir], sum = 0;
    if (was[i][j][lx][ly][dir]) return ans;
    if (i == lx || j == ly) return 0;
    was[i][j][lx][ly][dir] = true;
    if (dir == 0) {
        for(int tj = j - 1; j < ly; j++) {
            sum += a[i][j];
            ans = max(ans, DP(i + 1, j, lx, tj, 1) + sum);
        }
    } else
    if (dir == 1) {
        for(int ti = i - 1; i < lx; i++) {
            sum += a[i][j];
            ans = max(ans, DP(i, j - 1, ti, ly, 2) + sum);
        }
    } else
    if (dir == 2) {
        for(int tj = j + 1; j > ly; j--) {
            sum += a[i][j];
            ans = max(ans, DP(i - 1, j, lx, tj, 3) + sum);
        }
    }
    else {
        for(int ti = i + 1; i > lx; i--) {
            sum += a[i][j];
            ans = max(ans, DP(i, j + 1, ti, ly, 0) + sum);
        }
    }
    return ans;
}

int main() {
    cin >> m >> n;
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++)
            cin >> a[i][j];
    F[1][1][m + 1][n + 1][0] = a[1][1];
    int res = DP(1, 1, m + 1, n + 1, 0);
    cout << res << endl;
    return 0;
}

Code mẫu của RR

//Wishing myself a happy lunar new year with a lot of accept solutions
//Written by Nguyen Thanh Trung
//Algorithm by Nguyen Thanh Trung
{$R-,Q-}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=21;
var
  a,ngang,doc:array[0..MAXN,0..MAXN] of integer;
  d1,d2,d3,d4:array[0..MAXN,0..MAXN,0..MAXN,0..MAXN] of integer;
  f1,f2:text;
  m,n:integer;
procedure openF; inline;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF; inline;
begin
  close(f1); close(f2);
end;
procedure inp; inline;
var
  i,j:integer;
begin
  read(f1,m,n);
  for i:=1 to m do
    for j:=1 to n do read(f1,a[i,j]);
end;
procedure ans; inline;
begin
  writeln(f2,d1[1,1,m,n]);
end;
procedure update(var u:integer;v:integer);
begin
  u:=max(u,v);
end;
procedure solve;
var
  i,j,x,y,u1,u2,v1,v2:integer;
begin
  for i:=1 to m do
  for j:=1 to n do
    begin
      d1[i,j,i,j]:=a[i,j];
      d2[i,j,i,j]:=a[i,j];
      d3[i,j,i,j]:=a[i,j];
      d4[i,j,i,j]:=a[i,j];
    end;
  for i:=1 to m do
    for j:=1 to n do
      doc[i,j]:=doc[i-1,j]+a[i,j];
  for j:=1 to n do
    for i:=1 to m do
      ngang[i,j]:=ngang[i,j-1]+a[i,j];
  for x:=0 to m-1 do
  for y:=0 to n-1 do
  if (x>0) or (y>0) then
    for u1:=1 to m-x do
    for v1:=1 to n-y do
      begin
        u2:=u1+x;
        v2:=v1+y;
        {Tinh d1}
        d1[u1,v1,u2,v2]:=a[u1,v1];
        for i:=u1+1 to u2 do
          update(d1[u1,v1,u2,v2],doc[i,v1]-doc[u1-1,v1]);
        for j:=v1+1 to v2 do
          update(d1[u1,v1,u2,v2],ngang[u1,j]-ngang[u1,v1-1]);
        for j:=v1+1 to v2 do
          update(d1[u1,v1,u2,v2],ngang[u1,j]-ngang[u1,v1-1]+d2[u1+1,v1,u2,j]);
        {Tinh d2}
        d2[u1,v1,u2,v2]:=a[u1,v2];
        for i:=u1+1 to u2 do
          update(d2[u1,v1,u2,v2],doc[i,v2]-doc[u1-1,v2]);
        for j:=v1 to v2-1 do
          update(d2[u1,v1,u2,v2],ngang[u1,v2]-ngang[u1,j-1]);
        for i:=u1+1 to u2 do
          update(d2[u1,v1,u2,v2],doc[i,v2]-doc[u1-1,v2]+d3[u1,v1,i,v2-1]);
        {Tinh d3}
        d3[u1,v1,u2,v2]:=a[u2,v2];
        for i:=u1 to u2-1 do
          update(d3[u1,v1,u2,v2],doc[u2,v2]-doc[i-1,v2]);
        for j:=v1 to v2-1 do
          update(d3[u1,v1,u2,v2],ngang[u2,v2]-ngang[u2,j-1]);
        for j:=v1 to v2-1 do
          update(d3[u1,v1,u2,v2],ngang[u2,v2]-ngang[u2,j-1]+d4[u1,j,u2-1,v2]);
        {Tinh d4}
        d4[u1,v1,u2,v2]:=a[u2,v1];
        for j:=v1+1 to v2 do
          update(d4[u1,v1,u2,v2],ngang[u2,j]-ngang[u2,v1-1]);
        for i:=u1 to u2-1 do
          update(d4[u1,v1,u2,v2],doc[u2,v1]-doc[i-1,v1]);
        for i:=u1 to u2-1 do
          update(d4[u1,v1,u2,v2],doc[u2,v1]-doc[i-1,v1]+d1[i,v1+1,u2,v2]);
      end;
end;
procedure refine;
var
  i,j,sum:longint;
begin
  for i:=1 to m do
  for j:=1 to n do
    if a[i,j]<0 then exit;
  sum:=0;
  for i:=1 to m do
  for j:=1 to n do
    inc(sum,a[i,j]);
  writeln(sum); halt;
end;
begin
  openF;
  inp;
  refine;
  solve;
  ans;
  closeF;
end.

Code mẫu của hieult

#pragma comment(linker, "/STACK:16777216")

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
//#include<conio.h>
#define ep 0.000001
#define maxn 2002
#define base 1000000000
#define modunlo 111539786
#define oo 1000000002
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
#define ull unsigned long long

double const PI=4*atan(1);

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;

typedef long long int64;

int f[22][22][22][22][4], h[22][22] = {0}, c[22][22] = {0};
int n, m, x;

int tinh(int r1, int c1, int r2, int c2, int d){
    int &res = f[r1][c1][r2][c2][d];
    if(res > -111) return res;
    if(r1 > r2 || c1 > c2) return res = 0;
    res = -oo;
    if(d == 0){
        for(int i = c1; i <= c2; i++){
            int t = h[r1][i] - h[r1][c1 - 1];
            res = max(res, t);
            res = max(res, t + tinh(r1 + 1, c1, r2, i, 1));
        } 
    }
    else if(d == 1){
        for(int i = r1; i <= r2; i++){
            int t = c[i][c2] - c[r1 - 1][c2];
            res = max(res, t);
            res = max(res, t + tinh(r1, c1, i, c2 - 1, 2));
        }
    }
    else if(d == 2){
        for(int i = c2; i >= c1; i--){
            int t = h[r2][c2] - h[r2][i - 1];
            res = max(res, t);
            res = max(res, t + tinh(r1, i, r2 - 1, c2, 3));
        }
    }
    else{
        for(int i = r2; i >= r1; i--){
            int t = c[r2][c1] - c[i - 1][c1];
            res = max(res, t);
            res = max(res, t + tinh(i, c1 + 1, r2, c2, 0));
        }
    }
    return res;
}

int main(){
    //freopen("input.in","r",stdin);
    //freopen("output.out","w",stdout);
    scanf("%d %d", &n, &m);

    memset(f, -111, sizeof(f));

    for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++){
        scanf("%d",&x);
        h[i][j] = h[i][j - 1] + x;
        c[i][j] = c[i - 1][j] + x;
    }

    printf("%d",tinh(1, 1, n, m, 0));

}