Language: C++

#include <algorithm>
#include <cstdio>
#include <vector>
#include <string>
#define pb push_back
template <typename T1, typename T2> inline void umin(T1 &x, const T2 &y) { y < x ? (x = y) : 0; }
template <typename T1, typename T2> inline void umax(T1 &x, const T2 &y) { y > x ? (x = y) : 0; }
int lp[2005][2005], rp[2005][2005], ul[2005], ur[2005], tmp[2005][2005];
int sum_can[2005], sum_l[2005][2005], sum_r[2005][2005], sum_in[2005][2005];
int bottom[2005], top[2005], que[2005], can_go[2005], unique[2005];
int bel_mn[2005][2005], ans;
bool del[2005];
std::vector<int> vec[2005];
inline int calc_meet(int l, int r)
{
	int pos = bel_mn[l][r];
	if (pos <= bottom[l] && pos <= bottom[r])
		return pos;
	return 1e9;
}
inline int calc_cnt(int l, int r, int lim = 1e9)
{
	lim = std::min({lim, bottom[l], bottom[r]});
	if (calc_meet(l, r) > lim)
		return 0;
	return sum_can[lim] - sum_l[lim][l] - sum_r[lim][r] + sum_in[l][r];
}
template <typename mapT>
void work(const mapT &inp)
{
	mapT str = inp;
	int n = str.size(), m = str[0].size();
	if (n < m)
	{
		mapT str_new(m, std::string(n, '#'));
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
				str_new[j][i] = str[i][j];
		}
		str = str_new;
		std::swap(n, m);
	}
	if (m == 1)
	{
		int cur = 0;
		for (int i = 0; i < n; i++)
		{
			if (str[i][0] == '#')
				cur = 0;
			else
			{
				ans += (str[i][0] - '0') * cur;
				cur += str[i][0] - '0';
			}
		}
		return;
	}
	int hu = n >> 1, hd = n - hu;
	mapT up(str.begin(), str.begin() + hu), down(str.begin() + hu, str.end());
	work(up);
	work(down);
	up.pb(down[0]);
	for (int i = 0; i < hd; i++)
	{
		for (int j = 0; j < m; j++)
		{
			lp[i][j] = 1e9;
			rp[i][j] = -1e9;
		}
	}
	// lp & rp
	for (int i = 0; i < m; i++)
	{
		if (down[0][i] != '#')
			lp[0][i] = rp[0][i] = i;
	}
	for (int i = 0; i < hd; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (down[i][j] == '#')
				continue;
			if (i)
			{
				umin(lp[i][j], lp[i - 1][j]);
				umax(rp[i][j], rp[i - 1][j]);
			}
			if (j)
			{
				umin(lp[i][j], lp[i][j - 1]);
				umax(rp[i][j], rp[i][j - 1]);
			}
		}
	}
	// top
	for (int i = 0; i <= hu; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (up[i][j] == '#')
			{
				tmp[i][j] = 1e9;
				continue;
			}
			tmp[i][j] = i;
			if (i)
				umin(tmp[i][j], tmp[i - 1][j]);
			if (j)
				umin(tmp[i][j], tmp[i][j - 1]);
		}
	}
	for (int i = 0; i < m; i++)
		top[i] = tmp[hu][i];
	// bottom
	for (int i = hd - 1; i >= 0; i--)
	{
		for (int j = m - 1; j >= 0; j--)
		{
			if (down[i][j] == '#')
			{
				tmp[i][j] = -1e9;
				continue;
			}
			tmp[i][j] = i;
			if (i + 1 < hd)
				umax(tmp[i][j], tmp[i + 1][j]);
			if (j + 1 < m)
				umax(tmp[i][j], tmp[i][j + 1]);
		}
	}
	for (int i = 0; i < m; i++)
		bottom[i] = tmp[0][i];
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < m; j++)
			bel_mn[i][j] = 1e9;
	}
	for (int i = 0; i < hd; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (lp[i][j] <= rp[i][j])
				umin(bel_mn[lp[i][j]][rp[i][j]], i);
		}
	}
	for (int l = 0; l < m; l++)
	{
		for (int r = m - 1; r >= l; r--)
		{
			if (l)
				umin(bel_mn[l][r], bel_mn[l - 1][r]);
			if (r + 1 < m)
				umin(bel_mn[l][r], bel_mn[l][r + 1]);
		}
	}
	for (int i = 0; i < hd; i++)
	{
		sum_can[i] = 0;
		memset(sum_l[i], 0, m << 2);
		memset(sum_r[i], 0, m << 2);
	}
	for (int i = 0; i < m; i++)
		memset(sum_in[i], 0, m << 2);
	for (int i = 0; i < hd; i++)
	{
		if (i)
		{
			sum_can[i] = sum_can[i - 1];
			memcpy(sum_l[i], sum_l[i - 1], m << 2);
			memcpy(sum_r[i], sum_r[i - 1], m << 2);
		}
		for (int j = 0; j < m; j++)
		{
			if (lp[i][j] > rp[i][j])
				continue;
			int val = down[i][j] - '0';
			sum_can[i] += val;
			if (lp[i][j])
				sum_l[i][lp[i][j] - 1] += val;
			if (rp[i][j] + 1 < m)
				sum_r[i][rp[i][j] + 1] += val;
			if (lp[i][j] && rp[i][j] + 1 < m)
				sum_in[lp[i][j] - 1][rp[i][j] + 1] += val;
		}
	}
	for (int i = 0; i < hd; i++)
	{
		for (int j = m - 2; j >= 0; j--)
			sum_l[i][j] += sum_l[i][j + 1];
		for (int j = 1; j < m; j++)
			sum_r[i][j] += sum_r[i][j - 1];
	}
	for (int l = m - 1; l >= 0; l--)
	{
		for (int r = l; r < m; r++)
		{
			if (l + 1 < m)
				sum_in[l][r] += sum_in[l + 1][r];
			if (r)
				sum_in[l][r] += sum_in[l][r - 1];
			if (l + 1 < m && r)
				sum_in[l][r] -= sum_in[l + 1][r - 1];
		}
	}
	for (int i = 0; i < m; i++)
		can_go[i] = calc_cnt(i, i);
	for (int i = 0; i < hu; i++)
		vec[i].clear();
	for (int i = 0; i < m; i++)
	{
		del[i] = top[i] >= hu;
		if (!del[i])
			vec[top[i]].pb(i);
	}
	for (int i = m - 1; i >= 0; i--)
	{
		if (up[hu][i] == '#')
		{
			ul[i] = 1e9;
			ur[i] = -1e9;
			continue;
		}
		ul[i] = ur[i] = i;
		if (i + 1 < m)
			umax(ur[i], ur[i + 1]);
	}
	for (int i = hu - 1; i >= 0; i--)
	{
		for (int j = m - 1; j >= 0; j--)
		{
			if (up[i][j] == '#')
			{
				ul[j] = 1e9;
				ur[j] = -1e9;
				continue;
			}
			if (j + 1 < m)
			{
				umin(ul[j], ul[j + 1]);
				umax(ur[j], ur[j + 1]);
			}
		}
		int cur = 0, cl = 0, cr = -1, he = 0, ta = 0;
		for (int j = 0; j < m; j++)
		{
			if (ul[j] > ur[j])
				continue;
			while (cr < ur[j])
			{
				int x = ++cr;
				if (del[x])
					continue;
				if (he < ta)
				{
					cur -= unique[que[ta - 1]];
					unique[que[ta - 1]] -= calc_cnt(que[ta - 1], x);
					cur += unique[que[ta - 1]];
					if (bottom[que[ta - 1]] <= bottom[x])
						ta--;
				}
				while (he < ta && bottom[que[ta - 1]] <= bottom[x])
				{
					ta--;
					cur -= unique[que[ta - 1]];
					unique[que[ta - 1]] -= calc_cnt(que[ta - 1], x);
					unique[que[ta - 1]] += calc_cnt(que[ta - 1], x, bottom[que[ta]]);
					cur += unique[que[ta - 1]];
				}
				que[ta++] = x;
				unique[x] = can_go[x];
				cur += unique[x];
			}
			while (cl < ul[j])
			{
				int x = cl++;
				if (del[x])
					continue;
				cur -= unique[x];
				if (he < ta && que[he] == x)
					he++;
			}
			ans += (up[i][j] - '0') * cur;
		}
		for (int x : vec[i])
			del[x] = true;
	}
}
char str[2005];
int main()
{
	// freopen("AGC028-F.in", "r", stdin);
	int n;
	scanf("%d", &n);
	std::vector<std::string> inp;
	for (int i = 0; i < n; i++)
	{
		scanf("%s", str);
		inp.pb(std::string(str));
	}
	work(inp);
	printf("%d\n", ans);
	return 0;
}


Compiler output:
a.cc: In function 'void work(const mapT&)':
a.cc:160:17: error: there are no arguments to 'memset' that depend on a template parameter, so a declaration of 'memset' must be available [-fpermissive]
  160 |                 memset(sum_l[i], 0, m << 2);
      |                 ^~~~~~
a.cc:160:17: note: (if you use '-fpermissive', G++ will accept your code, but allowing the use of an undeclared name is deprecated)
a.cc:161:17: error: there are no arguments to 'memset' that depend on a template parameter, so a declaration of 'memset' must be available [-fpermissive]
  161 |                 memset(sum_r[i], 0, m << 2);
      |                 ^~~~~~
a.cc:164:17: error: there are no arguments to 'memset' that depend on a template parameter, so a declaration of 'memset' must be available [-fpermissive]
  164 |                 memset(sum_in[i], 0, m << 2);
      |                 ^~~~~~
a.cc:170:25: error: there are no arguments to 'memcpy' that depend on a template parameter, so a declaration of 'memcpy' must be available [-fpermissive]
  170 |                         memcpy(sum_l[i], sum_l[i - 1], m << 2);
      |                         ^~~~~~
a.cc:171:25: error: there are no arguments to 'memcpy' that depend on a template parameter, so a declaration of 'memcpy' must be available [-fpermissive]
  171 |                         memcpy(sum_r[i], sum_r[i - 1], m << 2);
      |                         ^~~~~~
a.cc: In instantiation of 'void work(const mapT&) [with mapT = std::vector<std::__cxx11::basic_string<char> >]':
a.cc:301:6:   required from here
  301 |         work(inp);
      |         ~~~~^~~~~
a.cc:160:23: error: 'memset' was not declared in this scope
  160 |                 memset(sum_l[i], 0, m << 2);
      |                 ~~~~~~^~~~~~~~~~~~~~~~~~~~~
a.cc:5:1: note: 'memset' is defined in header '<cstring>'; this is probably fixable by adding '#include <cstring>'
    4 | #include <string>
  +++ |+#include <cstring>
    5 | #define pb push_back
a.cc:161:23: error: 'memset' was not declared in this scope, and no declarations were found by argument-dependent lookup at the point of instantiation
  161 |                 memset(sum_r[i], 0, m << 2);
      |                 ~~~~~~^~~~~~~~~~~~~~~~~~~~~
a.cc:160:23: note: 'memset' declared here, later in the translation unit
  160 |                 memset(sum_l[i], 0, m << 2);
      |                 ~~~~~~^~~~~~~~~~~~~~~~~~~~~
a.cc:164:23: error: 'memset' was not declared in this scope
  164 |                 memset(sum_in[i], 0, m << 2);
      |                 ~~~~~~^~~~~~~~~~~~~~~~~~~~~~
a.cc:164:23: note: 'memset' is defined in header '<cstring>'; this is probably fixable by adding '#include <cstring>'
a.cc:170:31: error: 'memcpy' was not declared in this scope
  170 |                         memcpy(sum_l[i], sum_l[i - 1], m << 2);
      |                         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:170:31: note: 'memcpy' is defined in header '<cstring>'; this is probably fixable by adding '#include <cstring>'
a.cc:171:31: error: 'memcpy' was not declared in this scope, and no declarations were found by argument-dependent lookup at the point of instantiation
  171 |                         memcpy(sum_r[i], sum_r[i - 1], m << 2);
      |                         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:170:31: note: 'memcpy' declared here, later in the translation unit
  170 |                         memcpy(sum_l[i], sum_l[i - 1], m << 2);
      |                         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~