fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const double EPS = 1e-8;
  5. #define ll long long
  6. #define ld long double
  7. #define base 31
  8. #define mod 1000000007
  9. #define M 100005
  10. #define zero(x) memset(x,0,sizeof(x))
  11. #define oo INT_MAX
  12. #define fo(i,n) for(i=0;i<n;i++)
  13. #define foo(i,n) for(i=1;i<=n;i++)
  14. #define fa(i,I,n) for(i=I;i<n;i++)
  15. int n,m,t,sum[105][105],tmp[105];
  16. char ma[105][105];
  17. int inter(int a,int b){
  18.     if(a<0||b<0)return 0;
  19.     return sum[a][b];
  20. }
  21. int suma(int a,int b,int c,int d){
  22.     return inter(c,d)-inter(c,b-1)-inter(a-1,d)+inter(a-1,b-1);
  23. }
  24. int main(){
  25.     while(1){
  26.         ll sol=0;
  27.         scanf("%d",&n);
  28.         if(!n)break;
  29.         scanf("%d",&m);
  30.         zero(sum);
  31.         for(int i=0;i<n;i++)scanf("%s",ma[i]);
  32.         sum[0][0]=(ma[0][0]=='1'?1:0);
  33.         for(int i=1;i<m;i++)sum[0][i]=sum[0][i-1]+(ma[0][i]=='1'?1:0);
  34.         for(int i=1;i<n;i++){
  35.             tmp[0]=(ma[i][0]=='1'?1:0);
  36.             sum[i][0]=sum[i-1][0]+tmp[0];
  37.             for(int j=1;j<m;j++){
  38.                 tmp[j]=tmp[j-1]+(ma[i][j]=='1'?1:0);
  39.                 sum[i][j]=sum[i-1][j]+tmp[j];
  40.             }
  41.         }
  42.         for(int i=0;i<n;i++){
  43.             for(int j=0;j<m;j++){
  44.                 for(int k=j;k<m;k++){
  45.                     int a=i,b=n,p=(b+a)/2;
  46.                     while(b-a>1){
  47.                         if(suma(i,j,p-1,k)==(k-j+1)*(p-i)){
  48.                             a=p;
  49.                         }else{
  50.                             b=p;
  51.                         }
  52.                         p=(b+a)/2;
  53.                     }
  54.                     if(suma(i,j,b-1,k)==(k-j+1)*(b-i))p=b;
  55.                     if(suma(i,j,p-1,k)==(k-j+1)*(p-i)&&p>i){
  56.                         sol++;
  57.                         if(p-i>1)sol+=p-i-1;
  58.                     }
  59.                 }
  60.             }
  61.         }
  62.         printf("%lld\n",sol);
  63.     }
  64.     return 0;
  65. }
Success #stdin #stdout 0s 3192KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/4wvZTj
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!