Tontti

#include <iostream>
#include <string>

using namespace std;
typedef long long ll;

int n, m, x;
ll st[2005][2005];
ll res = 0;

ll sum(int y1, int x1, int y2, int x2) {
	ll cres = st[y2][x2];
	if (y1 > 0) cres -= st[y1-1][x2];
	if (x1 > 0) cres -= st[y2][x1-1];
	if (y1 > 0 && x1 > 0) cres += st[y1-1][x1-1];
	return cres;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m >> x;
	for (int i = 0; i < n; ++i) {
		string s;
		cin >> s;
		for (int j = 0; j < m; ++j) {
			if (s[j] == '*') {
				st[i][j] = 1;
			}
			if (j > 0) st[i][j] += st[i][j-1];
			if (i > 0) st[i][j] += st[i-1][j];
			if (i > 0 && j > 0) st[i][j] -= st[i-1][j-1];
		}
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			int mi = 0;
			for (int k = (1<<12); k >= 1; k /= 2) {
				while (i+k+mi < n && j+k+mi < m && sum(i, j, i+k+mi, j+k+mi) < x) mi += k;
			}
			if (sum(i, j, i+mi, j+mi) < x) mi++;
			if (sum(i, j, i+mi, j+mi) != x) continue;

			int mx = 0;
			for (int k = (1<<12); k >= 1; k /= 2) {
				while (i+k+mx < n && j+k+mx < m && sum(i, j, i+k+mx, j+k+mx) <= x) mx += k;
			}
			res += (mx-mi+1);
		}
	}
	cout << res << "\n";
	return 0;
}

Test 1

Group: 1

Verdict: ACCEPTED

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: ACCEPTED

Test 12

Group: 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 3

Verdict: ACCEPTED