oj.uz

답안 #206266

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
206266 2020-03-02T21:57:37 Z luciocf Strah (COCI18_strah) C++14
33 / 110
 174 ms 6136 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 <= n; i++)
		S[i] = S[i-1] + 1ll*i*(i+1)/2;

	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]*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:25: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:29: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
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Incorrect 5 ms 380 KB Output isn't correct

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 1912 KB Output is correct
2 Correct 15 ms 1912 KB Output is correct

Subtask #4
11.0 / 11.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 1912 KB Output is correct
2 Correct 15 ms 1916 KB Output is correct

Subtask #6
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 124 ms 5496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 124 ms 3320 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 174 ms 6136 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 15 ms 1528 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 131 ms 3448 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -