Submission #3880758

---

Source Code Expand

#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;

int main()
{
	LL H, W, N, M;
	in >> H >> W >> N >> M;
	std::vector<std::string>A(N);
	rep(i, N) in >> A[i];

	std::vector<std::vector<int>>field(std::min(H, N * 2 + 1) + 1, std::vector<int>(std::min(W, M * 2 + 1) + 1));
	rep(i, N)
	{
		rep(j, M)
		{
			if (A[i][j] == '#')
			{
				++field[i][j];
				--field[field.size() - (N - i)][j];
				--field[i][field[i].size() - (M - j)];
				++field[field.size() - (N - i)][field[i].size() - (M - j)];
			}
		}
	}
	rep(i, field.size() - 1) rep(j, field[i].size()) field[i + 1][j] += field[i][j];
	rep(i, field.size()) rep(j, field[i].size() - 1) field[i][j + 1] += field[i][j];

	std::map<LL, LL>h, w;
	bool h_over = field.size() != H + 1, w_over = field[0].size() != W + 1;
	rep(i, field.size() - 1)
	{
		if (h_over && i == N) h[i] = H - 2 * N;
		else h[i] = 1;
	}
	rep(j, field[0].size() - 1)
	{
		if (w_over && j == M) w[j] = W - 2 * M;
		else w[j] = 1;
	}

	LL ans = 0;
	rep(i, field.size()) rep(j, field[i].size()) if (field[i][j] > 0) ans += h[i] * w[j];

	out << ans << std::endl;
}

Submission Info

Judge Result