oj.uz

Submission #206339

# Submission time Handle Problem Language Result Execution time Memory
206339 2020-03-03T01:50:25 Z luciocf Strah (COCI18_strah) C++14
110 / 110
 439 ms 24056 KB 
#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);
}

Compilation message

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2552 KB Output is correct
2 Correct 15 ms 2424 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2552 KB Output is correct
2 Correct 15 ms 2424 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2552 KB Output is correct
2 Correct 15 ms 2552 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 8448 KB Output is correct
2 Correct 265 ms 17656 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 13984 KB Output is correct
2 Correct 420 ms 23084 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 8696 KB Output is correct
2 Correct 292 ms 18792 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 12280 KB Output is correct
2 Correct 311 ms 21884 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 417 ms 22008 KB Output is correct
2 Correct 439 ms 24056 KB Output is correct