Submission #1165622

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165622		sleepntsheep	Strah (COCI18_strah)	C11	110 / 110	89 ms	22088 KiB

strah

#include <stdio.h>

#define N 2222

long long z;
char s[N][N];
int y, n, m, h[N][N], sta[N], top, l[N], r[N];

void dfs(int u, int ll, int rr) {
	if (ll > rr)
		return;

	long long L = u - ll, R = rr - u;

	z += ((R + 1) * (L + 2) * (L + 1) / 2
			+ (L + 1) * (R + 0)  * (R + 1) / 2) * (h[y][u] * (h[y][u] + 1ll) / 2);

	dfs(l[u], ll, u - 1);
	dfs(r[u], u + 1, rr);
}

int main() {
	scanf("%d%d", &n, &m);

	for (int i = 1; i <= n; ++i) {
		scanf("%s", s[i] + 1);
		for (int j = 1; j <= m; ++j) {
			l[j] = r[j] = 0;
			h[i][j] = h[i - 1][j] + (s[i][j] == '.');
			if (s[i][j] == '#')
				h[i][j] = 0;
		}

		top = 0;
		for (int j = 1; j <= m; ++j) {
			int k = top;

			while (k && h[i][sta[k]] > h[i][j]) {
				--k;
			}

			if (k + 1 <= top) {
				l[j] = sta[k + 1];
			}
			if (k)
				r[sta[k]] = j;

			sta[top = ++k] = j;

		}

		y = i;
		dfs(sta[1], 1, m);
	}



	printf("%lld\n", z);
	return 0;
}

Compilation message (stderr)

strah.c: In function 'main':
strah.c:23:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         scanf("%d%d", &n, &m);
      |         ^~~~~~~~~~~~~~~~~~~~~
strah.c:26:17: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |                 scanf("%s", s[i] + 1);
      |                 ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 11 / 11
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 11 / 11
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11