글 읽기 - 20%에서 실패) 반례나 오류 있을까요?

korea_ac 1년 전 0

6549 히스토그램에서 가장 큰 정사각형 스택이용해서 풀었습니다.

기존 올라온 반례에서는 전부 통과하고 오류 찾아도 안보이고 전부 long long으로 사용해서 범위오류도 안생길텐데

20%에서 항상 오류가 생깁니다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stack>
#include <cstdio>

using namespace std;
int main()
{
	while (1)
	{
		long long h;
		long long n = 0;
		scanf("%lld", &n);
		if (n == 0) return 0;
		long long answer = 0;

		stack <long long> stk1;// 높이
		stack <long long> stk2;// 가로위치

		for (long long i = 0; i < n; i++) {
			scanf("%lld", &h);
			if (stk1.empty())
			{
				stk1.push(h);
				stk2.push(i);
			}
			else if (h >= stk1.top())
			{
				stk1.push(h);
				stk2.push(i);
			}
			else
			{
				long long temp_i = 0;
				while (!stk1.empty() && stk1.top() > h)
				{
					long long temp_h = stk1.top();
					temp_i = stk2.top();
					stk1.pop();
					stk2.pop();

					long long rect = (i - temp_i)*temp_h;
					if (rect > answer)
						answer = rect;
				}
				stk1.push(h);
				stk2.push(temp_i);
			}


		}
		

		while (!stk1.empty())
		{
			long long temp_h = stk1.top();
			long long temp_i = stk2.top();
			stk1.pop();
			stk2.pop();

			long long rect = (n - temp_i)*temp_h;
			if (rect > answer)
				answer = rect;
		}
		printf("%lld", answer);
	}

	return 0;
}

g072923 1년 전 1

각 출력마다 개행문자를 넣어주셔야합니다

korea_ac 1년 전 0

감사합니다

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

문제

문제

출처

ICPC

20%에서 실패) 반례나 오류 있을까요?

korea_ac 1년 전 0

g072923 1년 전 1

korea_ac 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말