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>
using namespace std;

int row[222][222],col[222][222],a[222][222],m,n;

int countCells(int x,int xx,int y,int yy)
{
    if (x==xx || y==yy) return xx-x+yy-y+1;
    return 2*(xx-x+yy-y);
}

void updateAns(int val,int cntVal,int &ans,int &cnt)
{
    if (val>ans) ans=val, cnt=cntVal;
    else cnt+=(ans==val)*cntVal;
}

int main()
{
    int test;
    cin >> test;
    while (test--)
    {
        cin >> m >> n;
        for (int i=1;i<=m;i++)
            for (int j=1;j<=n;j++)
            {
                scanf("%d",a[i]+j);
                row[i][j]=row[i][j-1]+a[i][j];
                col[i][j]=col[i-1][j]+a[i][j];
            }

        int ans=-m*n,cnt=0;

        for (int i=1;i<=m;i++)
            for (int j=0;j<n;j++)
                for (int jj=j+1;jj<=n;jj++)
                    updateAns((row[i][jj]-row[i][j])*2-(jj-j),1,ans,cnt);

        for (int i=0;i<m;i++)
            for (int ii=i+2;ii<=m;ii++)
            {
                int maxCol=-m*n,cntCol=0;
                for (int j=1;j<=n;j++)
                {
                    int cur=(col[ii][j]-col[i][j])*2-(ii-i);
                    int side=(a[ii][j]+a[i+1][j])*2-2;
                    updateAns(cur,1,ans,cnt);
                    updateAns(cur+maxCol,cntCol,ans,cnt);
                    maxCol+=side;
                    if (cur>maxCol) maxCol=cur, cntCol=1;
                    else cntCol+=(cur==maxCol);
                }
            }

        cout << ans << ' ' << cnt << endl;
    }
}

Code mẫu của happyboy99x

#include<iostream>
using namespace std;

const int N = 500, INF = 1e9;
int a[N][N], s[N + 1][N];

void update(int &best, int &cnt, int x, int nway = 1) {
    if(x > best) best = x, cnt = 0;
    if(x == best) cnt += nway;
}

int main() {
    ios::sync_with_stdio(false);
    int numTest; cin >> numTest;
    for(int test = 0; test < numTest; ++test) {
        int m, n; cin >> m >> n;
        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                cin >> a[i][j];
                if(a[i][j] == 0) a[i][j] = -1;
                s[i + 1][j] = s[i][j] + a[i][j];
            }
        }
        int best = -INF, cnt = 0;
        for(int i = 0; i < m; ++i)
            for(int j = 0; j < n; ++j) {
                int sum = a[i][j];
                update(best, cnt, sum);
                for(int k = j + 1; k < n; ++k)
                    update(best, cnt, sum += a[i][k]);
                sum = a[i][j];
                for(int k = i + 1; k < m; ++k)
                    update(best, cnt, sum += a[k][j]);
            }
        for(int top = 0; top < m; ++top)
            for(int bot = top + 1; bot < m; ++bot) {
                int prev = -INF, nway = 1;
                for(int i = 0; i < n; ++i) {
                    int r = s[bot + 1][i] - s[top][i];
                    update(best, cnt, r + prev, nway);
                    if(r > prev + a[top][i] + a[bot][i]) {
                        prev = r, nway = 1;
                    } else {
                        if(r == prev + a[top][i] + a[bot][i]) ++nway;
                        prev = prev + a[top][i] + a[bot][i];
                    }
                }
            }
        cout << best << ' ' << cnt << '\n';
    }
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>
const int N = 222;
const int oo = 1000000009;
using namespace std;
int a[N][N], col[N][N], row[N][N], res, m, n, cnt, cmin, minS;

void Upd(int sum) {
    if (res < sum) {
        res = sum;
        cnt = cmin;
    } else
    if (res == sum) cnt += cmin;
}

void Updm(int sum) {
    if (minS > sum) {
        minS = sum;
        cmin = 1;
    } else
    if (minS == sum) cmin++;
}

void Enter() {
    int i, j, s;
        for(i=1; i<=m; i++)
            for(j=1; j<=n; j++) {
                scanf("%d", &a[i][j]);
                if (a[i][j] == 0) a[i][j] = -1;
                col[i][j] = col[i-1][j] + a[i][j];
                row[i][j] = row[i][j-1] + a[i][j];
            }

        for(j=1; j<=n; j++) {
            s = 0; minS = 0; cmin = 1;
            for(i=1; i<=m; i++) {
                s += a[i][j];
                Upd(s - minS);
                Updm(s);
            }
        }
        for(i=1; i<=m; i++) {
            minS = 0; cmin = 1;
            for(j=2; j<=n; j++) {
                s = row[i][j];
                Upd(s - minS);
                Updm(row[i][j-1]) ;
            }
        }
}

int main()
{
    //freopen("MATRIX.in", "r",stdin);
    int i, j, k, t, s;
    scanf("%d\n", &t);
    while (t--) {
        scanf("%d %d\n", &m, &n);
        res = -oo; cnt = 0;
        Enter();
        for(i=1; i<=m; i++)
            for(j=i+1; j<=m; j++) {
                minS = col[i][1] - col[j-1][1];
                cmin = 1;
                for(k=2; k<=n; k++) {
                    s = row[i][k] + row[j][k] + col[j-1][k] - col[i][k];
                    Upd(s - minS);
                    Updm(row[i][k-1] + row[j][k-1] - col[j-1][k] + col[i][k]);
                }
            }
        printf("%d %d\n", res, cnt);
    }
    return 0;
}

Code mẫu của RR

{$R-,Q-}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=201;
var
  f1,f2:text;
  kq,count,test,t,m,n:longint;
  sum,a:array[-1..MAXN,-1..MAXN] of longint;
  nn,sl:array[0..MAXN] of longint;
procedure openF;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
  close(f1); close(f2);
end;
procedure swap(var a,b:longint);
var
  temp:longint;
begin
  temp:=a; a:=b; b:=temp;
end;
procedure inp; inline;
var
  i,j:longint;
begin
  read(f1,m,n);
  if n=1 then swap(m,n);
  kq:=-1;
  for i:=1 to m do
  for j:=1 to n do
    begin
      read(f1,a[i,j]);
      if a[i,j]=0 then a[i,j]:=-1
      else if a[i,j]=1 then kq:=1;
    end;
end;
procedure ans;
begin
  writeln(f2,kq,' ',count);
end;
procedure solve1;
var
  i:longint;
begin
  for i:=1 to n do
    sum[1,i]:=sum[1,i-1]+a[1,i];
  nn[0]:=sum[1,0]; sl[0]:=1;
  for i:=1 to n do
    if sum[1,i]<nn[i-1] then
      begin
        sl[i]:=1;
        nn[i]:=sum[1,i];
      end
    else if sum[1,i]=nn[i-1] then
      begin
        sl[i]:=sl[i-1]+1;
        nn[i]:=nn[i-1];
      end
    else
      begin
        nn[i]:=nn[i-1];
        sl[i]:=sl[i-1];
      end;
  for i:=1 to n do
    kq:=max(kq,sum[1,i]-nn[i-1]);
  count:=0;
  for i:=1 to n do
    if sum[1,i]-nn[i-1]=kq then inc(count,sl[i-1]);
end;
procedure cal; inline;
var
  i,j:longint;
begin
  for i:=1 to m do
  for j:=1 to n do
    sum[i,j]:=sum[i,j-1]+sum[i-1,j]-sum[i-1,j-1]+a[i,j];
end;
function get(i1,v1,i2,v2:longint):longint; inline;
begin
  if i1>i2 then exit(0);
  if v1>v2 then exit(0);
  get:=sum[i2,v2]-sum[i1-1,v2]-sum[i2,v1-1]+sum[i1-1,v1-1];
end;
procedure solve2;
var
  i1,i2,i,j,gt:longint;
begin
  cal;
  for i1:=1 to m do
  for i2:=i1 to m do
    begin
      nn[0]:=-get(i1+1,1,i2-1,1); sl[0]:=1;
      for j:=1 to n-1 do
        begin
          gt:=get(i1,1,i2,j)-get(i1+1,1,i2-1,j+1);
          if gt<nn[j-1] then
            begin
              nn[j]:=gt;
              sl[j]:=1;
            end
          else if gt=nn[j-1] then
            begin
              nn[j]:=gt;
              sl[j]:=sl[j-1]+1;
            end
          else {gt>nn[j-1]}
            begin
              nn[j]:=nn[j-1];
              sl[j]:=sl[j-1];
            end;
        end;
      for j:=2 to n do
        begin
          gt:=get(i1,1,i2,j);
          gt:=gt-get(i1+1,1,i2-1,j-1);
          gt:=gt-nn[j-2];
          if gt>kq then
            begin
              kq:=gt;
              count:=sl[j-2];
            end
          else if kq=gt then inc(count,sl[j-2]);
        end;
    end;
  for j:=1 to n do
    begin
      fillchar(nn,sizeof(nn),0); fillchar(sl,sizeof(sl),0);
      sl[0]:=1;
      for i:=1 to m do
        if nn[i-1]<sum[i,j]-sum[i,j-1] then
          begin
            nn[i]:=nn[i-1];
            sl[i]:=sl[i-1];
          end
        else if nn[i-1]=sum[i,j]-sum[i,j-1] then
          begin
            nn[i]:=nn[i-1];
            sl[i]:=sl[i-1]+1;
          end
        else
          begin
            nn[i]:=sum[i,j]-sum[i,j-1];
            sl[i]:=1;
          end;
      for i:=1 to m do
        begin
          gt:=sum[i,j]-sum[i,j-1]-nn[i-1];
          if gt>kq then begin kq:=gt; count:=sl[i-1]; end
          else if gt=kq then inc(count,sl[i-1]);
        end;
    end;
end;
begin
  openF;
  read(f1,t);
  for test:=1 to t do
    begin
      inp; count:=0; kq:=-maxlongint;
      if (m=1) and (n=1) then
        begin
          if a[1,1]=1 then writeln(f2,'1 1')
          else writeln(f2,'-1 1');
          continue;
        end;
      if (m>1) then solve2
      else solve1;
      ans;
    end;
  closeF;
end.

Code mẫu của hieult

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <algorithm>

#include <ctime>
#include <deque>
#include <bitset>
#include <cctype>
#include <utility>
#include <cassert>

using namespace std;

typedef long long ll;
typedef double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

#define Rep(i,n) for(int i = 0; i < (n); ++i)
#define Repd(i,n) for(int i = (n)-1; i >= 0; --i)
#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 Fit(i,v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
#define Fitd(i,v) for(__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
#define ms(a,x) memset(a, x, sizeof(a))

template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; }
template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T> T sqr(T x) { return x * x; }
template<class T> T cube(T x) { return x * x * x; }
template<class T> int getbit(T s, int i) { return (s >> i) & 1; }
template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
template<class T> int cntbit(T s) { return s == 0 ? 0 : cntbit(s >> 1) + (s & 1); }

typedef pair<int, int> II;

const double PI = acos(-1.0);
const double eps = 1e-9;

const int dr[] = {-1, 0, +1, 0};
const int dc[] = {0, +1, 0, -1};

const int inf = (int)1e9 + 5;
const ll linf = (ll)1e16 + 5;
const ll mod = (ll)1e9 + 7;

#define maxn 205

int test, n, m, a[maxn][maxn], r[maxn][maxn], c[maxn][maxn], f[maxn], g[maxn];

int main(){
//    freopen("in.txt", "r", stdin);

    scanf("%d", &test);
    Rep(itest, test){
        scanf("%d %d", &n, &m);
        For(i, 1, n) {
            For(j, 1, m){
                scanf("%d", &a[i][j]);
                if(a[i][j] == 0) a[i][j] = -1;
            }
        }

        ms(c, 0); ms(r, 0);
        For(i, 1, n) For(j, 1, m){
            r[i][j] = r[i][j - 1] + a[i][j];
            c[i][j] = c[i - 1][j] + a[i][j];
        }

        int res = -inf, A;
        ll num = 0, so;

        For(i, 1, n){
            int MIN = 0, so = 1;
            For(j, 1, m){
                A = r[i][j] - MIN;
                if(A == res) num += so;
                if(A > res){
                    num = so;
                    res = A;
                }
                if(r[i][j] == MIN) so++;
                if(r[i][j] < MIN){
                    MIN = r[i][j];
                    so = 1;
                }
            }
        }

        For(j, 1, m){
            int MIN = 0, so = 1;
            For(i, 2, n){
                A = c[i][j] - MIN;
                if(A == res) num += so;
                if(A > res){
                    num = so;
                    res = A;
                }
                if(c[i - 1][j] == MIN) so++;
                if(c[i - 1][j] < MIN){
                    MIN = c[i - 1][j];
                    so = 1;
                }
            }
        }

        For(u, 1, n) For(v, u + 1, n){
            f[0] = g[0] = 0;
            For(i, 1, m) {
                f[i] = r[u][i] + r[v][i];
                g[i] = c[v - 1][i] - c[u][i];
            }

            int MAX = g[1] - f[0]; so = 1;
            For(i, 2, m){
                A = g[i] + f[i] + MAX;
                if(A == res) num += so;
                if(A > res){
                    num = so;
                    res = A;
                }
                if(g[i] - f[i - 1] == MAX) so++;
                if(g[i] - f[i - 1] > MAX){
                    MAX = g[i] - f[i - 1];
                    so = 1;
                }
            }
        }
        cout << res << " " << num << endl;

    }

    return 0;
}

Code mẫu của skyvn97

#include<bits/stdc++.h>
#define  MAX   211
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define FORD(i,b,a) for (int i=(b);i>=(a);i=i-1)
#define REP(i,n) for (int i=0;i<(n);i=i+1)
#define fi   first
#define se   second
using namespace std;
typedef pair<int,int> ii;
int m,n;
int prev[MAX];
int a[MAX][MAX],s[MAX][MAX];
ii tmp[MAX];
void update(ii &a,const ii &b) {
    if (a.fi<b.fi) a=b;
    else if (a.fi==b.fi) a.se+=b.se;
}
void init(void) {
    scanf("%d",&m);
    scanf("%d",&n);
    FOR(i,1,m) FOR(j,1,n) {
        scanf("%d",&a[i][j]);
        if (a[i][j]<1) a[i][j]=-1;
        s[i][j]=s[i-1][j]+a[i][j];
    }
}
ii tworow(int x,int y) {
    //printf("CHOOSE %d %d\n",x,y);
    ii ret=ii(-2,0);
    if (x==y) {
        ii here=ii(a[x][1],1);
        update(ret,here);
        FOR(i,2,n) {
            if (here.fi<0) here=ii(a[x][i],1);
            else here=ii(here.fi+a[x][i],here.se+(here.fi==0));
            update(ret,here);
        }
        //printf("CHOOSE %d %d is %d %d\n",x,y,ret.fi,ret.se);
        return (ret);
    }
    if (x+1==y) {
        ii here=ii(a[x][1]+a[y][1],1);
        update(ret,here);
        FOR(i,2,n) {
            if (here.fi<0) here=ii(a[x][i]+a[y][i],1);
            else here=ii(here.fi+a[x][i]+a[y][i],here.se+(here.fi==0));
            update(ret,here);
        }
        //printf("CHOOSE %d %d is %d %d\n",x,y,ret.fi,ret.se);
        return (ret);
    }
    int sx=a[x][1];
    int sy=a[y][1];
    int fst=1;
    int lst=0;
    FOR(i,2,n) {
        sx+=a[x][i];
        sy+=a[y][i];
        ii cur=ii(sx+sy+s[y-1][1]-s[x][1]+s[y-1][i]-s[x][i],i);
        while (fst<=lst && tmp[lst].fi<cur.fi) lst--;
        lst++;
        tmp[lst]=cur;
    }
    FORD(i,lst,fst) if (i==lst || tmp[i].fi>tmp[i+1].fi) prev[i]=1; else prev[i]=prev[i+1]+1;
    update(ret,ii(tmp[fst].fi,prev[fst]));
    int delta=0;
    FOR(i,2,n-1) {
        while (fst<=lst && tmp[fst].se<=i) fst++;
        assert(fst<=lst);
        delta+=-(s[y][i-1]-s[x-1][i-1])+(s[y-1][i]-s[x][i]);
        update(ret,ii(tmp[fst].fi+delta,prev[fst]));
    }
    FOR(i,1,n) update(ret,ii(s[y][i]-s[x-1][i],1));
    return (ret);
}
void process(void) {
    ii res=ii(-2,0);
    FOR(i,1,m) FOR(j,i,m) update(res,tworow(i,j));
    printf("%d %d\n",res.fi,res.se);
}
int main(void) {
#ifndef ONLINE_JUDGE
    freopen("tmp.txt","r",stdin);
#endif
    int t;
    scanf("%d",&t);
    REP(zz,t) {
        init();
        process();
    }
    return 0;
}