Submission #3981748

---

Source Code Expand

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
long long solve(vector<string> S) {
	int H = S.size(), W = S[0].size();
	vector<vector<int> > sum(H + W - 1, vector<int>(H + 1));
	for (int i = 0; i <= H + W - 2; ++i) {
		for (int j = 0; j < H; ++j) {
			sum[i][j + 1] = sum[i][j] + (0 <= i - j && i - j < W && S[j][i - j] == '#' ? 1 : 0);
		}
	}
	long long ans = 0;
	for (int i = 0; i <= H + W - 2; ++i) {
		for (int j = i + 2; j <= H + W - 2; j += 2) {
			int B = (j - i) / 2;
			for (int k = 0; k < H - B; ++k) {
				if (i - k >= W || i - k - B < 0 || S[k][i - k] == '.' || S[k + B][i - k - B] == '.') continue;
				int llim = max(k + B, j - W + 1);
				int rlim = min({ k + 2 * B, H - 1, j }) + 1;
				ans += (sum[j][rlim] - sum[j][llim]) * 2;
				ans -= (0 <= j - (k + B) && j - (k + B) < W && S[k + B][j - (k + B)] == '#' ? 1 : 0);
				ans -= (k + 2 * B < H && 0 <= j - (k + 2 * B) && j - (k + 2 * B) < W && S[k + 2 * B][j - (k + 2 * B)] == '#' ? 1 : 0);
			}
		}
	}
	return ans;
}
vector<string> rotate(vector<string> S) {
	int H = S.size(), W = S[0].size();
	vector<string> ans(W, string(H, '?'));
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			ans[j][H - i - 1] = S[i][j];
		}
	}
	return ans;
}
int main() {
	int H, W;
	cin >> H >> W;
	vector<string> S(H);
	for (int i = 0; i < H; ++i) {
		cin >> S[i];
	}
	long long ans = 0;
	for (int i = 0; i < 4; ++i) {
		ans += solve(S);
		S = rotate(S);
	}
	cout << ans / 2 << endl;
	return 0;
}

Submission Info

Judge Result