oj.uz

Submission #206313

# Submission time Handle Problem Language Result Execution time Memory
206313 2020-03-03T01:00:54 Z luciocf Strah (COCI18_strah) C++14
55 / 110
 168 ms 4600 KB 
#include <bits/stdc++.h>

#define ff first
#define ss second

using namespace std;

const int maxn = 1e3+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;

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

			ans += 1ll*x;
		}
	}

	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 17 ms 2100 KB Output is correct
2 Correct 15 ms 1784 KB Output is correct

Subtask #4
11.0 / 11.0

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

Subtask #5
11.0 / 11.0

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

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 123 ms 4472 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 132 ms 1412 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 168 ms 4600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 15 ms 1272 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 139 ms 1272 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -