제출 #206339

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
206339		luciocf	Strah (COCI18_strah)	C++14	110 / 110	439 ms	24056 KiB

strah

#include <bits/stdc++.h>

#define ff first
#define ss second

using namespace std;

const int maxn = 2e3+10;

typedef pair<int, int> pii;
typedef long long ll;

int n, m;
char tab[maxn][maxn];

int h[maxn][maxn];

int l[maxn], r[maxn];

ll S[maxn];

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

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			scanf(" %c", &tab[i][j]);

	for (int i = 1; i <= max(n, m); i++)
		S[i] = S[i-1] + (1ll*i*(i+1))/2ll;

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (tab[i][j] == '#') h[i][j] = 0;
			else h[i][j] = h[i-1][j]+1;
		}
	}

	ll ans = 0;

	for (int i = 1; i <= n; i++)
	{
		stack<pii> stk;

		for (int j = 1; j <= m; j++)
		{
			while (stk.size() && stk.top().ff >= h[i][j])
				stk.pop();

			if (stk.size()) l[j] = stk.top().ss+1;
			else l[j] = 1;

			stk.push({h[i][j], j});
		}

		while (stk.size()) stk.pop();

		for (int j = m; j >= 1; j--)
		{
			while (stk.size() && stk.top().ff > h[i][j])
				stk.pop();

			if (stk.size()) r[j] = stk.top().ss-1;
			else r[j] = m;

			stk.push({h[i][j], j});
		}

		for (int j = 1; j <= m; j++)
		{
			int a = j-l[j], b = r[j]-j;
			int tot = r[j]-l[j]+1;

			ans += (1ll*h[i][j]*(1ll*h[i][j]+1ll)/2ll)*(S[tot] - S[a] - S[b]);
		}
	}

	printf("%lld\n", ans);
}

컴파일 시 표준 에러 (stderr) 메시지

strah.cpp: In function 'int main()':
strah.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
strah.cpp:28:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf(" %c", &tab[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~~~~

• 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