글 읽기 - 뭐가 틀린 걸까요???

mung3477 4년 전 0

나름 알고리즘은 맞는 것 같고.. 주어진 예제 및 만들어본 샘플들은 다 맞는데요.

대체 뭐가 틀려서 틀렸습니다 를 받는지 모르겠네요 ㅠㅠㅠㅠㅠ

#include <stdio.h>
#include <algorithm>
#include <stack>
using namespace std;

stack<int> blocks;
long long int block[100001];
long long int AreaByThis[100001];

int main(void)
{
	while (1) {
		long long int t = 0;
		int n;
		scanf("%d", &n);
		
		if (n == 0) break;

		/*블럭 높이 저장*/
		for (int i = 1; i <= n; i++) {
			scanf("%lld", &block[i]);
		}

		/*각 블럭을 이용해 우측으로 만들 수 있는 넓이*/
		for (int i = 1; i <= n; i++) {
			while (!blocks.empty()) {
				if (block[blocks.top()] <= block[i]) {
					break;
				}

				else {
					AreaByThis[blocks.top()] = block[blocks.top()] * (i - blocks.top());
					blocks.pop();
				}
			}
			blocks.push(i);
		}

		if (!blocks.empty()) t = blocks.size();

		while (!blocks.empty()) {
			AreaByThis[blocks.top()] = block[blocks.top()] * (t - blocks.size() + 1);
			blocks.pop();
		}

		/*각 블럭이 좌측으로 만들 수 있는 넓이. 합칠 거라서 넓이에서 블럭 한 번 빼줌*/
		for (int i = n; i >= 1; i--) {
			while (!blocks.empty()) {
				if (block[blocks.top()] <= block[i]) {
					break;
				}

				else {
					AreaByThis[blocks.top()] += block[blocks.top()] * (blocks.top() - i - 1);
					blocks.pop();
				}
			}
			blocks.push(i);
		}

		if (!blocks.empty()) t = blocks.size();

		while (!blocks.empty()) {
			AreaByThis[blocks.top()] += block[blocks.top()] * (t - blocks.size());
			blocks.pop();
		}

		/*가장 큰 넓이 찾기. Bubble sort를 1회만.*/
		t = 0;
		for (int i = 1; i <= n - 1; i++) {
			if (AreaByThis[i] > AreaByThis[i + 1]) {
				t = AreaByThis[i];
				AreaByThis[i] = AreaByThis[i + 1];
				AreaByThis[i + 1] = t;
			}
		}

		printf("%lld\n", AreaByThis[n]);
	}

	return 0;
}

sait2000 4년 전 0

반례 드립니다.

in:
3 3 4 3
0

out:
9

mung3477 4년 전 0

오 그러네요. 감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

뭐가 틀린 걸까요???

mung3477 4년 전 0

sait2000 4년 전 0

mung3477 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말