글 읽기 - 분할정복 20% 시간 초과 문제입니다.

swrho 1년 전 1

int 타입 대신에 long long 타입을 사용하였습니다.

게시판의 반례를 통과합니다.

뭐가 잘못된건지 찾아봐도 잘 모르겠네요,,

로직이 잘못된건가요??

#include <iostream>
#include <algorithm>
#include <memory.h>

using namespace std;

int N, H[100005];
long long result;
long long histogram(int s, int e) { // s ~ e-1 까지의 히스토그램 직사각형 최댓값
	if (s == e) return 0;
	if (s + 1 == e) return H[s];
	int weight = 1, mid = (s + e) / 2;
	int left = mid, right = mid, curH = H[mid];
	long long leftResult = histogram(s, mid);
	long long rightResult = histogram(mid, e);
	long long result2 = max(leftResult, rightResult);
	long long result = weight * curH;
	while (0 <= left && right <= N - 1) {
		int leftH = 0, rightH = 0, tempH = 0;
		if (left - 1 >= 0)
			leftH = H[left - 1];
		else leftH = 0;
		if (right + 1 <= N - 1)
			rightH = H[right + 1];
		else rightH = 0;
		if (leftH == 0 && rightH == 0) break;
		if (leftH >= rightH) { // 왼쪽으로 확장
			left--;
			tempH = leftH;
		}
		else {
			right++;
			tempH = rightH;
		}
		curH = min(curH, tempH);
		weight++;
		result = max(result, ((long long)weight) * (long long)curH);
	}
	return max(result2, result);
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	//freopen("input.txt", "r", stdin);
	do {
		cin >> N;
		if (N == 0)	break;
		for (int i = 0; i < N; i++)
			cin >> H[i];
		cout << histogram(0, N) << "\n";
	} while (1);
}

dosawas 1년 전 1

지금은 분할정복 마다 0~n-1까지 다 검사를 합니다 s~e구간까지만 검사해도 됩니다.

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

문제

문제

출처

ICPC

분할정복 20% 시간 초과 문제입니다.

swrho 1년 전 1

dosawas 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말