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

const fi='';
      fo='';
      maxn=1010;
var n,m:longint;
    re:int64;
    f,st:array[0..maxn] of longint;
    num:array[0..maxn] of int64;

procedure pr;
var i,j,now,t:longint; c:char;
begin
     assign(input,fi);
     reset(input);
     readln(m,n);
     re:=0;
     fillchar(f,sizeof(f),0);
     for i:=1 to m do
     begin
          for j:=1 to n do
          begin
               read(c);
               if c='0' then f[j]:=0 else inc(f[j]);
          end;
          readln;
          num[0]:=0; f[0]:=-1; st[0]:=0; now:=0;
          for j:=1 to n do
          begin
               while f[st[now]]>=f[j] do dec(now);
               t:=st[now];
               inc(now);
               st[now]:=j;
               num[j]:=f[j]*(j-t)+num[t];
               re:=re+num[j];
          end;
     end;
     close(input);
end;

procedure wf;
begin
     assign(output,fo);
     rewrite(output);
     write(re);
     close(output);
end;

begin
     pr;
     wf;
end.

Code mẫu của happyboy99x

#include<cstdio>

const int N = 1005;

/* Stack */
int stack[N], topS;
void init() { topS = 0; }
int top() { return stack[topS-1]; }
int pop() { return stack[--topS]; }
void push(const int &x) { stack[topS++] = x; }
/* End of Stack */

int m, n, f[N][N], left[N];
long long dp[N];
char a[N][N];
/* f[y][x] = k <=> a[y..y+k-1][x] = 11..., k max */

void enter() {
    scanf("%d%d",&m,&n);
    for(int i = 0; i < m; ++i)
        scanf("%s", a[i]);
}

void calcF() {
    for(int j = 0; j < n; ++j)
        for(int i = m-1; i >= 0; --i)
            f[i][j] = a[i][j] == 0x31 ? f[i+1][j] + 1 : 0;
}

void solve() {
    long long res = 0;
    for(int i = 0; i < m; ++i) {
        left[0] = 0; init();
        for(int j = 1; j < n; ++j)
            if(f[i][j] > f[i][j-1]) left[j] = j, push(j-1);
            else {
                while(topS && f[i][j] <= f[i][top()]) pop();
                left[j] = topS ? top() + 1 : 0;
            }
        for(int j = 0; j < n; ++j) res += dp[j] = (left[j] == 0 ? 0 : dp[left[j]-1]) + (j - left[j] + 1) * f[i][j];
    }
    printf("%lld\n", res);
}

int main() {
    enter();
    calcF();
    solve();
    return 0;
}

Code mẫu của ladpro98

#include <iostream>

using namespace std;

const int N = 1010;

char a[N];
int c[N][N];
int h[N];
int s[N];
int size;

int n, m;

int main() {
    cin >> m >> n;
    for (int i = 1; i <= m; ++i) {
        cin >> (a + 1);
        for (int j = 1; j <= n; ++j) h[j] = a[j] == '1' ? h[j] + 1 : 0;
        size = 0;
        for (int j = 0; j <= n + 1; ++j) {
            while (size && h[s[size]] >= h[j]) {
                int w = j - 1 - s[size - 1];
                ++c[max(h[s[size - 1]], h[j]) + 1][w];
                --c[h[s[size]] + 1][w];
                --size;
            }
            s[++size] = j;
        }
    }
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) c[i + 1][j] += c[i][j];
        int cur = 0;
        for (int j = n; j >= 1; --j) {
            cur += c[i][j];
            c[i][j] = c[i][j + 1] + cur;
        }
    }
    long long ans = 0;
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            ans += c[i][j];
    cout << ans << endl;
}

Code mẫu của RR

//Written by RR
{$IFDEF RR}
  {$R+,Q+,S+}
  {$inline off}
  {$Mode objFPC}
{$ELSE}
  {$R-,Q-}
  {$inline on}
  {$Mode objFPC}
{$ENDIF}
uses math;
const
  FINP          =       {$IFDEF RR} 'input.txt';  {$ELSE} ''; {$ENDIF}
  FOUT          =       {$IFDEF RR} 'output.txt'; {$ELSE} ''; {$ENDIF}
  MAXN          =       1111;
var
  f1,f2         :       text;
  m,n           :       longint;
  a             :       array[1..MAXN,1..MAXN] of byte;
  h,stack       :       array[0..MAXN] of longint;
  left,right    :       array[0..MAXN] of longint;
  ok            :       array[0..MAXN] of boolean;

procedure openF;
    begin
      assign(f1,FINP); reset(f1);
      assign(f2,FOUT); rewrite(f2);
    end;
procedure closeF;
    begin
      close(f1);
      close(f2);
    end;
procedure inp;
    var
      i,j:longint;
      ch:char;
    begin
      readln(f1,m,n);
      for i:=1 to m do
        begin
          for j:=1 to n do
            begin
              read(f1,ch);
              if ch='0' then a[i,j]:=0 else a[i,j]:=1;
            end;
          readln(f1);
        end;
    end;
procedure solve;
    var
      count:int64;
      i,j,k:longint;
      l,r:longint;
      top:longint;
    begin
      count:=0;
      for i:=1 to m do
        begin
          for j:=1 to n do
            if a[i,j]=1 then inc(h[j]) else h[j]:=0;

          top:=0; stack[0]:=0;
          for j:=1 to n do
            begin
              while (top>0) and (h[stack[top]]>=h[j]) do dec(top);
              left[j]:=stack[top]+1;
              inc(top); stack[top]:=j;
            end;

          top:=0; stack[0]:=n+1;
          for j:=n downto 1 do
            begin
              while (top>0) and (h[stack[top]]>=h[j]) do dec(top);
              right[j]:=stack[top]-1;
              inc(top); stack[top]:=j;
            end;

          top:=0; stack[0]:=0;
          for j:=1 to n do
            begin
              while (top>0) and (h[stack[top]]>h[j]) do dec(top);
              if h[stack[top]]=h[j] then ok[j]:=false else ok[j]:=true;
              inc(top); stack[top]:=j;
            end;

          {$IFDEF RR}
          writeln(f2);
          writeln(f2,'=============');
          writeln(f2,'Hang ',i);
          for j:=1 to n do write(f2,h[j],' '); writeln(f2);
          writeln(f2,'left: ');
          for j:=1 to n do write(f2,left[j],' '); writeln(f2);
          writeln(f2,'right: ');
          for j:=1 to n do write(f2,right[j],' '); writeln(f2);
          writeln(f2,'ok: ');
          for j:=1 to n do
            if ok[j] then write(f2,'1 ') else write(f2,'0 ');
          writeln(f2);
          writeln(f2,'============');
          writeln(f2);
          {$ELSE}
          {$ENDIF}
          for j:=1 to n do
          if ok[j] then
            begin
              l:=left[j]; r:=right[j];
              k:=max(h[l-1],h[r+1]);
              inc(count,(r-l+1)*(r-l+2)*(h[j]-k)>>1);
              {$IFDEF RR}
              writeln(f2,'   cot ',j);
              writeln(f2,'     left = ',l,' right = ',r,' count+= ',(r-l+1)*(r-l+2)*(h[j]-k)>>1);
              {$ELSE}
              {$ENDIF}
            end;
        end;
      writeln(f2,count);
    end;

begin
  openF;
  inp;
  solve;
  closeF;
end.

Code mẫu của hieult

#include <cstdio>
#include <cstring>
//#include <conio.h>
int m,n,chay,
   h[1002],s[1002];
long long KQ, soh[1002];
char a[1002];

int main()
{
    //freopen("CREC01.in","r",stdin);
    scanf("%d %d",&m,&n);
    gets(a);
    for(int i  = 1;i<=m;i++)
    {
        gets(a);
        for(int j = 1;j<=n;j++)
        {
            if(a[j-1]=='0') h[j]=0;
            else h[j]++;
        }
        int chay = 0;s[0] = 0; soh [0] = 0; h[0] = -1;
        for(int j = 1;j<=n;j++)
        {
            while(h[s[chay]]>=h[j]) chay--;
            int flag = s[chay];
            s[++chay] = j;
            soh[j] = h[j]*(j-flag) + soh[flag];
            KQ = KQ+soh[j];
        }
    }
    printf("%lld",KQ);
    //getch();
}

Code mẫu của ll931110

#include <iostream>
#include <cstring>
#define MAXN 1001

int stack[MAXN],h[MAXN],m,n;
long long res,calc[MAXN];
char s[MAXN];

int main()
{
    int i,j,top,tmp;

    //freopen("crec01.inp","r",stdin);
    //freopen("crec01.out","w",stdout);

    scanf("%d%d", &m, &n);
    res = 0;
    gets(s);

    h[0] = -1;
    for (i = 1; i <= m; i++)
      {
           gets(s);
           for (j = 1; j <= n; j++)
             if (s[j - 1] == '1') h[j]++;
               else h[j] = 0;

           top = 0;
           for (j = 1; j <= n; j++)
             {
               while (h[stack[top]] >= h[j]) top--;
               tmp = stack[top];

               calc[j] = (j - tmp) * h[j] + calc[tmp];
               res += calc[j];

               top++;
               stack[top] = j;
             }
      }

    printf("%lld", res);
}

Code mẫu của skyvn97

#include<cstdio>
#include<stack>
#define MAX   1010
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define REP(i,n) for (int i=0;i<(n);i=i+1)
using namespace std;
char a[MAX][MAX];
int h[MAX][MAX];
int l[MAX];
int c[MAX][MAX];
int m,n;
stack<int> st;
void init(void) {
    scanf("%d",&m);
    scanf("%d",&n);
    FOR(i,1,m) {
        scanf("%s",a[i]+1);
        FOR(j,1,n) {
            if (a[i][j]=='1') h[i][j]=h[i-1][j]+1;
            else h[i][j]=0;
        }
    }
}
void count(void) {
    FOR(i,1,m) {
        while (!st.empty()) st.pop();
        l[1]=1;
        c[i][1]=h[i][1];            
        FOR(j,2,n) {
            if (h[i][j]>h[i][j-1]) {
                l[j]=j;
                st.push(j-1);
            }
            else {
                while (!st.empty() && h[i][st.top()]>=h[i][j]) st.pop();
                if (st.empty()) l[j]=1;
                else l[j]=st.top()+1;
            }
            c[i][j]=c[i][l[j]-1]+h[i][j]*(j-l[j]+1);
        }
    }
    long long res=0;
    FOR(i,1,m) FOR(j,1,n) res+=c[i][j];
    printf("%lld",res);
}
int main(void) {
    init();
    count();
    return 0;
}

Code mẫu của khuc_tuan

//{$APPTYPE CONSOLE}
 {$MODE DELPHI}

var
    m, n, i, j, t : integer;
    a : array[0..1001] of char;
    h, l, c : array[0..1001] of integer;
    r : int64;
begin
    readln(m,n);
    r := 0;
    for i:=1 to m do
    begin
        readln(a);
        for j:=0 to n-1 do
        begin
            if a[j]='0' then h[j] := 0
            else inc(h[j]);
            t := j-1;
            while (t >= 0) and (h[t] >= h[j]) do t := l[t];
            l[j] := t;
            c[j] := (j-t) * h[j];
            if t >= 0 then c[j] := c[j] + c[t];
            r := r + c[j];
        end;
    end;
    writeln(r);
end.