글 읽기 - 뭐가 틀린걸까요 ㅠㅜ

wlshddlek 5년 전 0

왜 틀렸는지 모르겠네요 테스트케이스와 반례들도 다 통과한거같은데 ㅠ

#include<iostream>
#include<algorithm>
using namespace std;
int n;
int buffer[100002];
int tree[210000]; 
void init(int start, int end, int node)  //각 구간에 제일 높이가 작은 index값을 갖는 세그먼트 트리 초기화
{
	if (start == end)
	{
		tree[node] = start;
		return;
	}
	int mid = (start + end) / 2;
	init(start, mid, 2 * node);
	init(mid + 1, end, 2 * node + 1);
	
	if (buffer[tree[node*2]] < buffer[tree[node*2+1]])tree[node]=tree[node*2];
	else tree[node] = tree[node * 2+1];

}
int get_min(int start, int end, int node, int left, int right)//해당범위에서 가장 작은 높이 index 반환
{
	if (end<left || start>right)return -1;
	if (start >= left && end <= right)return tree[node];

	int mid = (start + end) / 2;
	int a = get_min(start, mid, 2 * node,left, right);
	int b = get_min(mid + 1,end, 2 * node+ 1, left, right);

	if (a == -1)return b;   //a가 범위 밖이면 b반환
	if (b == -1)return a;
	if (buffer[a] < buffer[b])return a;   //둘중에 높이가 작은거 반환
	else return b;
	
}
long long int get_maxarea(int start, int end)     //최대넓이 구하기
{
	
	int minn = get_min(0,n-1,1,start,end);     //해당구간의 최소 높이
	long long int area = (long long int)buffer[minn] * (end - start + 1);
	if (start < minn)               //최소index의 왼쪽이 존재하면 
	{
		area=max(area,get_maxarea(start, minn - 1));
	}
	if (end > minn)                  //최소 index의 오른쪽이 존재하면
	{
		area=max(area,get_maxarea(minn + 1, end));
	}
	return area;
}
int main()
{
	while (1)
	{
		cin >> n;
		if (n == 0)break;
		for (int i = 0; i < n; i++)
		{
			cin >> buffer[i];
		}
		init(0, n - 1, 1);
		long long int result = get_maxarea(0, n - 1);
		printf("%lld\n", result);
	}
	return 0;
}

wlshddlek 5년 전 0

아우씨 보니까 트리 배열공간을 작게 만들었었네요,,,,,

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

문제

문제

출처

ICPC

뭐가 틀린걸까요 ㅠㅜ

wlshddlek 5년 전 0

wlshddlek 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말