Submission #588294

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;

#define sum(_r1,_r2,_c1,_c2,_wa) (_wa[_r2][_c2]+_wa[_r1-1][_c1-1]-_wa[_r2][_c1-1]-_wa[_r1-1][_c2])
#define sum2(_r1,_r2,_c1,_c2,_wa,i) (_wa[_r2][_c2][i]+_wa[_r1-1][_c1-1][i]-_wa[_r2][_c1-1][i]-_wa[_r1-1][_c2][i])

int main() {
    int R,C,K;
    cin>>R>>C>>K;
    vector<string> S(R);
    for(auto& it : S)cin>>it;
    VV wa(R+1,V(C+1,0));
    VVV num(R+1,VV(C+1,V(10,0)));

    {
        for(int r = 0; r < R; r++)
            for(int c = 0; c < C; c++){
                wa[r+1][c+1]=S[r][c]-'0';
                num[r+1][c+1][wa[r+1][c+1]]=1;
            }
        for(int r = 1; r <= R; r++)
            for(int c = 1; c <= C; c++){
                wa[r][c]+=wa[r][c-1]+wa[r-1][c]-wa[r-1][c-1];
                for(int i = 0; i < 10; i++){
                    num[r][c][i]+=num[r][c-1][i]+num[r-1][c][i]-num[r-1][c-1][i];
                }
            }
    }
    LL res=0;
    for(int r1 = 1; r1 <= R; r1++)
        for(int r2 = r1+2; r2 <= R; r2++)
            for(int c1 = 1; c1 <= C-2; c1++){
                int c2=c1+2;
                if(sum(r1,r2,c1,c2,wa)-K<=0){
                    if(sum(r1,r2,c1,C,wa)-K<=0)break;;
                    int bottom=c1+2,top=C;
                    while(top-bottom>1){
                        int m=(top+bottom)>>1;
                        if(sum(r1,r2,c1,m,wa)-K>=0)top=m;
                        else bottom=m;
                    }
                    c2=top;
                }
                for(; c2 <= C; c2++){
                    int sa=sum(r1,r2,c1,c2,wa)-K;
                    if(sa>=10)break;
                    res+=sum2(r1+1,r2-1,c1+1,c2-1,num,sa);
                }
            }
    cout<<res<<endl;
    return 0;
}

Submission Info

Judge Result