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>
#include <cstdio>
#define oo 1000111222
#define fr(a,b,c) for (a=b;a<=c;a++)
#define frr(a,b,c) for (a=b;a>=c;a--)
using namespace std;

int m,n,k,re,a[333][333],Col_Min[333][333],Col_Max[333][333],Bot_Right[333][333],Top_Left[333][333];

void calc(int f[333][333])
{
    int i,h,j;
    fr(i,1,m)
        frr(h,i,1)
        {
            fr(j,1,n)
            {
                Col_Min[i][j]=min(Col_Min[i][j],a[h][j]);
                Col_Max[i][j]=max(Col_Max[i][j],a[h][j]);
                if (Col_Max[i][j]-Col_Min[i][j]>k) continue;
                int jj=j-1, Max=Col_Max[i][j], Min=Col_Min[i][j];
                while (jj && max(Max,Col_Max[i][jj])-min(Min,Col_Min[i][jj])<=k) 
                {
                    Max=max(Max,Col_Max[i][jj]);
                    Min=min(Min,Col_Min[i][jj]);
                    jj--;
                }
                f[i][j]=max(f[i][j],(i-h+1)*(j-jj));
            }
        }
    fr(i,1,m) fr(j,1,n) f[i][j]=max(f[i][j],max(f[i][j-1],f[i-1][j]));
}

void Reverse()
{
    int i,j;
    fr(i,1,(m+1)/2) 
        fr(j,1,(i*2<=m?n:n/2))
        {
            int t=a[i][j];
            a[i][j]=a[m+1-i][n+1-j];
            a[m+1-i][n+1-j]=t;
        }
}

int main()
{
    int i,j;
    cin >> m >> n >> k;
    fr(i,1,m) fr(j,1,n) scanf("%d",&a[i][j]);

    fr(i,1,m) fr(j,1,n) Col_Min[i][j]=Col_Max[i][j]=a[i][j];
    calc(Bot_Right);

    Reverse();
    fr(i,1,m) fr(j,1,n) Col_Min[i][j]=Col_Max[i][j]=a[i][j];
    calc(Top_Left);

    fr(i,1,m) fr(j,1,n)
    {
        if (i<m) re=max(re,Bot_Right[i][j]+Top_Left[m-i][n]);
        if (j<n) re=max(re,Bot_Right[i][j]+Top_Left[m][n-j]);
    }
    cout << re << endl;
    return 0;
}

Code mẫu của ladpro98

program BLAND;
uses
    math;
const
    MAXN = 303;
    INFINTY = trunc(2e9);
var
    m, n, maxDiff: longint;
    a, b: array[0..MAXN, 0..MAXN] of longint;
    minA, maxA, Q_max, Q_min, down, up: array[0..MAXN] of longint;

function sweep(row: longint): longint;
var
    l_max, l_min, r_max, r_min: longint;
    i, j: longint;
    answer: longint;
begin
    l_max := 1; l_min := 1;
    r_max := 0; r_min := 0;
    j := 1;
    answer := 0;
    for i := 1 to n do
    begin
        maxA[i] := max(maxA[i], a[row, i]);
        minA[i] := min(minA[i], a[row, i]);
        while (r_max >= l_max) and (maxA[Q_max[r_max]] <= maxA[i]) do dec(r_max);
        while (r_min >= l_min) and (minA[Q_min[r_min]] >= minA[i]) do dec(r_min);
        inc(r_max); Q_max[r_max] := i;
        inc(r_min); Q_min[r_min] := i;
        while (j <= i) and ((maxA[Q_max[l_max]] - minA[Q_min[l_min]]) > maxDiff) do
        begin
            inc(j);
            if (l_max <= r_max) and (Q_max[l_max] < j) then inc(l_max);
            if (l_min <= r_min) and (Q_min[l_min] < j) then inc(l_min);
        end;
        answer := max(answer, i - j + 1);
    end;
    exit(answer);
end;    

function solve(): longint;
var
    i, j: longint;
    current, answer: longint;
begin
    answer := 0;
    for i := 1 to m do
    begin
        up[i] := 0;
        down[i] := 0;
    end;
    for i := 1 to m do
    begin
        for j := 1 to n do
        begin
            maxA[j] := -INFINTY;
            minA[j] := INFINTY;
        end;
        for j := i to m do
        begin
            current := sweep(j) * (j - i + 1);
            down[i] := max(down[i], current);
            up[j] := max(up[j], current);
        end;
        for j := 2 to m do
        begin
            answer := max(answer, up[j - 1] + down[j]);
            up[j] := max(up[j], up[j - 1]);
        end;
    end;
    exit(answer);
end;

procedure rotate();
var
    save: longint;
    i, j: longint;
begin
    for i := 1 to m do for j := 1 to n do
        b[j, i] := a[i, j];
    save := m; m := n; n := save;
    for i := 1 to m do for j := 1 to n do
        a[i, j] := b[i, j];
end;

procedure main();
var
    i, j: longint;
    firstSolve, secondSolve: longint;
begin
    read(m, n, maxDiff);
    for i := 1 to m do for j := 1 to n do read(a[i, j]);
    firstSolve := solve();
    rotate();
    secondSolve := solve();
    writeln(max(firstSolve, secondSolve));
end;

begin
    main();
end.

Code mẫu của RR

#include <iostream>
#include <algorithm>
#define FOR(i,a,b)  for(int i=a; i<=b; i++)
#define FORD(i,a,b) for(int i=a; i>=b; i--)
#define MAXN 311
using namespace std;

int m,n,k;
int up_[MAXN],down_[MAXN],left_[MAXN],right_[MAXN];
int h[MAXN][MAXN];
int ln[10][10][MAXN][MAXN],nn[10][10][MAXN][MAXN];
int val[520];
int nhan[MAXN][MAXN];

void inp() {
    scanf("%d %d %d",&m,&n,&k);
    FOR(i,1,m)
    FOR(j,1,n)
        scanf("%d",&h[i][j]);
}

void RMQ() {
    FOR(i,1,m)
    FOR(j,1,n)
        ln[0][0][i][j]=nn[0][0][i][j]=h[i][j];

    FOR(lj,1,9)
        FOR(i,1,m)
        FOR(j,1,n-(1<<lj)+1) {
            ln[0][lj][i][j]=max(ln[0][lj-1][i][j],ln[0][lj-1][i][j+(1<<(lj-1))]);
            nn[0][lj][i][j]=min(nn[0][lj-1][i][j],nn[0][lj-1][i][j+(1<<(lj-1))]);
        }

    FOR(li,1,9)
        FOR(i,1,m-(1<<li)+1)
        FOR(j,1,n) {
            ln[li][0][i][j]=max(ln[li-1][0][i][j],ln[li-1][0][i+(1<<(li-1))][j]);
            nn[li][0][i][j]=min(nn[li-1][0][i][j],nn[li-1][0][i+(1<<(li-1))][j]);
        }

    FOR(li,1,9)
    FOR(lj,1,9)
        FOR(i,1,m-(1<<li)+1)
        FOR(j,1,n-(1<<lj)+1) {
            ln[li][lj][i][j]=max(ln[li][lj-1][i][j],ln[li][lj-1][i][j+(1<<(lj-1))]);
            nn[li][lj][i][j]=min(nn[li][lj-1][i][j],nn[li][lj-1][i][j+(1<<(lj-1))]);
        }
}

inline int get(int i1,int i2,int j1,int j2) {
    int ki=val[i2-i1+1];
    int kj=val[j2-j1+1];
    int tmp1=j2-(1<<kj)+1;
    int tmp2=i2-(1<<ki)+1;

    return max(max(ln[ki][kj][i1][j1],ln[ki][kj][i1][tmp1]),
               max(ln[ki][kj][tmp2][j1],ln[ki][kj][tmp2][tmp1]))
          -min(min(nn[ki][kj][i1][j1],nn[ki][kj][i1][tmp1]),
               min(nn[ki][kj][tmp2][j1],nn[ki][kj][tmp2][tmp1]));     
}

void init() {
    FOR(i,0,300)
    FOR(j,0,300)
        nhan[i][j]=i*j;
}

void solve() {
    FOR(i,0,9) val[1<<i]=i;
    FOR(i,2,511) if (!val[i]) val[i]=val[i-1];

    FOR(l,1,m)
    FOR(r,l,m) {
        int jj=1;
        FOR(j,1,n) {
            while (jj<=j && get(l,r,jj,j)>k) jj++;
            if (jj>j) continue;
            int now=nhan[r-l+1][j-jj+1];
            up_[l] >?= now;
            down_[r] >?= now;
            left_[j] >?= now;
            right_[jj] >?= now;
        }
    }

    FOR(i,2,m) down_[i] >?= down_[i-1];
    FORD(i,m-1,1) up_[i] >?= up_[i+1];

    FOR(i,2,n) left_[i] >?= left_[i-1];
    FORD(i,n-1,1) right_[i] >?= right_[i+1];

//    FOR(i,1,m) cout<<down_[i]<<" "<<up_[i]<<endl;
//    FOR(i,1,n) cout<<left_[i]<<" "<<right_[i]<<endl;

    int res=0;
    FOR(i,1,m-1) res >?= down_[i]+up_[i+1];
    FOR(i,1,n-1) res >?= left_[i]+right_[i+1];

    cout<<res;
}

int main() {
    inp();
    RMQ();
    init();
    solve();
    return 0;
}

Code mẫu của khuc_tuan

#include <cstdio>

#include <algorithm>

using namespace std;



int m, n, k, result;

int a[303][303], b[303][303];

int F[303][303], end[303], start[303];

int mm[303], MM[303];



pair<int,int> qmin[303], qmax[303];

int lmin, rmin, lmax, rmax;



void add(pair<int,int> p, pair<int,int> qmin[303], int &L, int &R) {

    while(L<=R && qmin[R] > p) --R;

    qmin[++R] = p;

}



void process() {

    memset( F, 0, sizeof(F));

    memset( start, 0, sizeof(start));

    memset( end, 0, sizeof(end));

    for(int i=0;i<m;++i) {

        memset( mm, 0x1f, sizeof(mm));

        memset( MM, 0xAF, sizeof(MM));

        for(int i2=i;i2<m;++i2) {

            int st = 0;

            lmin = lmax = 1;

            rmin = rmax = 0;

            for(int j=0;j<n;++j) {

                mm[j] <?= a[i2][j];

                MM[j] >?= a[i2][j];

                add( make_pair(mm[j], j), qmin, lmin, rmin);

                add( make_pair(-MM[j], j), qmax, lmax, rmax);

                for(;st <= j && -qmin[lmin].first-qmax[lmax].first > k;++st) {

                    if(qmin[lmin].second == st) ++lmin;

                    if(qmax[lmax].second == st) ++lmax;

                }   

                if(st <= j) F[i][i2] >?= j - st + 1;

            }

            start[i] >?= F[i][i2] * (i2 + 1 - i);

            end[i2] >?= F[i][i2] * (i2 + 1 - i);

        }

    }

    for(int i=1;i<m;++i) end[i] >?= end[i-1];

    for(int i=m-2;i>=0;--i) start[i] >?= start[i+1];

    for(int i=0;i+1<m;++i) result >?= end[i] + start[i+1];

}



int main() {

    scanf("%d%d%d", &m, &n, &k);

    for(int i=0;i<m;++i)

        for(int j=0;j<n;++j)

            scanf("%d", a[i] + j);



    process();

    for(int i=0;i<m;++i)

        for(int j=0;j<n;++j)

            b[j][i] = a[i][j];

    memmove( a, b, sizeof(a));

    swap(m,n);

    process();

    printf("%d\n", result);

    return 0;

}