ACMICPC 6549
/*
입력은 테스트 케이스 여러 개로 이루어져 있다.
각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000)
그 다음 n개의 정수 h1, …, hn (0 ≤ hi ≤ 1000000000)가 주어진다. 이 숫자들은 히스토그램에 있는 직사각형의 높이이며,
왼쪽부터 오른쪽까지 순서대로 주어진다. 모든 직사각형의 너비는 1이고, 입력의 마지막 줄에는 0이 하나 주어진다.
입력
7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0
출력
8
4000
*/
#include
#include “memory.h”
#define MAX_BUF 100000+10
typedef struct my_stack{
unsigned long long length;
int position;
}my_stack;
my_stack buff[MAX_BUF] = { 0, };
int end = 0;
int main(void)
{
int test_count=1;
while (test_count)
{
//init buff
memset(buff, 0, sizeof(buff));
end = 0;
unsigned long long input = 0;
unsigned long long max = 0;
scanf(“%d”, &test_count);
if (test_count == 0) break;
scanf(“%lld”, &input);
buff[end].length = input;
buff[end].position = 0;
//end++;
for (int i = 1; i < test_count; i++)
{
scanf(“%lld”, &input);
if (buff[end].length < input)
{
//insert buffer
end++;
buff[end].length = input;
buff[end].position = i;
}
else if (buff[end].length == input)
{
//skip
}
else if (buff[end].length > input)
{
//length가 input보다 작은곳까지 줄이고 input 을 넣는다.
//줄이는 겨웅 max값 계산.
int backup = 0;
while (buff[end].length > input)
{
if (max < buff[end].length * (i - buff[end].position ))
max = buff[end].length * (i - buff[end].position);
backup = buff[end].position;
end–;
}
end++;
buff[end].length = input;
buff[end].position = backup;
}
}
// 마지막 남은 buffer들의 크기를 구해서 max값을 구한다.
while (buff[end].length > 0)
{
if (max < buff[end].length * (test_count - buff[end].position))
max = buff[end].length * (test_count - buff[end].position);
end–;
}
printf(“%lld\n”, max);
}
return 0;
}