CREC01 – SPOJ

const   fi      ='';
        fo      ='';
        oo      =1000;
 
var     a       :array[0..oo,0..oo] of 0..1;
        l,h,dem:array[0..oo+1] of int64;
        m, n    :longint;
 
procedure Optimize;
var     i, j    :longint;
        ans     :int64;
begin
        fillchar(h, sizeof(h),0);
        ans:=0;
        for i:=1 to m do
                begin
                        for j:=1 to n do
                                begin
                                        if a[i,j]=1 then begin
                                        l[j]:=j;
                                        h[j]:=h[j]+1;
                                        while h[l[j]-1]>h[j] do
                                                l[j]:=l[l[j]-1];
                                        dem[j]:=h[j]*(j-l[j]+1)+dem[l[j]-1];
                                        ans:=ans+dem[j];
                                        //writeln(ans,'==');
                                        //if (i=3) and (j=2) then writeln(dem[1]);
                                        end
                                        else begin
                                                dem[j]:=0;
                                                l[j]:=0;
                                                h[j]:=0;
                                        end;
 
                                end;
 
                end;
        writeln(ans);
end;
 
procedure run;
var     i, j, tg    :longint;
        s       :ansistring;
begin
        assign(input,fi);assign(output,fo);
        reset(input);rewrite(output);
        readln(m, n);
        for i:=1 to m do
                begin
                        readln(s);
                        for j:=1 to n do
                                        val(s[j],a[i,j]);
                end;
        Optimize;
        close(input);close(output);
 
end;
 
begin
        run;
end.

using namespace std;
#include<bits/stdc++.h>
 
#define BG begin()
#define ED end()
#define st first
#define nd second
#define PB push_back
#define PF push_front
#define FOR(i,a,b) for (long long i=a;i<b;i++)
#define FORE(i,a,b) for (long long i=a;i<=b;i++)
#define FORD(i,a,b) for (long long i=a;i>=b; i--)
#define ri(n)({
    int neg=0;
    n=0;
    char ch;
    for(ch=getchar(); ch<'0' || ch>'9'; ch=getchar()) if (ch=='-') neg=1-neg;
    n=ch-48;
    for(ch=getchar(); ch>='0' && ch<='9'; ch=getchar()) n=(n<<3)+(n<<1)+ch-48;
    if (neg) n=-n;
})
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> II;
typedef pair<ll,ll> LL;
const ll INF=1000000000+7;
const double esp=1e-13;
const double pi=3.141592653589;
 
 
ll m, n, a[1001][1001], H[1001], dem[1001], L[1001];
 
int main()
{
    //freopen("CREC01.inp", "r", stdin);
    //freopen("CREC01.out", "w", stdout);
    cin>>m>>n;
    char ch;
    FORE(i, 1, m)
        FORE(j, 1, n) {
            cin>>ch;
            a[i][j] = ch - '0';
        }
    memset(H, 0, sizeof(H));
    memset(L, 0, sizeof(L));
    memset(dem, 0, sizeof(dem));
    long long ans = 0;
    FORE(i, 1, m)
        FORE(j, 1, n) {
            //cout<<i<<" "<<j<<" "<<a[i][j]<<endl;
            if (a[i][j] == 1) {
                H[j]++;
                int k = j;
                while ( (k > 1) && (a[i][k-1] == 1) && (H[ k - 1 ] >= H[j]) ) k = L[k - 1];
                L[j] = k;
                dem[j] = H[j]*(j - L[j] + 1) + dem[L[j] - 1];
                ans += dem[j];
                //cout<<i<<"=="<<j<<"=="<<"=="<<H[j]<<"=="<<ans<<endl;
            }
            else
            {
                H[j] = 0;
                dem[j]= 0;
                L[j] = 0;
            }
        }
    cout<<ans;
}