Tontti

#include <algorithm>
#include <iostream>
#include <vector>

int main(){
  int n,m,x;std::cin>>n>>m>>x;
  std::vector<std::vector<int>>C(n+1,std::vector<int>(m+1));
  for(int i=1;i<=n;++i){
    for(int j=1;j<=m;++j){
      char c;std::cin>>c;
      C[i][j]=C[i][j-1]+C[i-1][j]-C[i-1][j-1];
      C[i][j]+=c=='*';
    }
  }
  #define TREES(i,j,z) C[i][j]-C[i][(j)-(z)]-C[(i)-(z)][j]+C[(i)-(z)][(j)-(z)]
  int count=0;
  for(int i=1;i<=n;++i){
    for(int j=1;j<=m;++j){
      int maxz=std::min(i,j);
      int hi=0,lo=0;
      for(int step=maxz/2;step;step/=2){
	while(hi+step<=maxz&&TREES(i,j,hi+step)<=x)++hi;
	while(lo+step<=maxz&&TREES(i,j,lo+step)<x)++lo;
      }
      if(TREES(i,j,hi)!=x)continue;
      count+=hi-lo;
    }
  }
  std::cout<<count<<'\n';
}

Test 1

Group: 1

Verdict: WRONG ANSWER

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 2

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED