글 읽기 - 39%에서 계속 '틀렸습니다' 가 뜹니다ㅠㅠ 고수님들 도와주세여...

kimbregas 6년 전 0

히스토그램을

분할정복으로 푸는 방식과 비슷하게 풀었습니다.

39%에서 자꾸 틀렸다고 나오는 데, 도저히 어떤 부분이 잘못되었는지 모르겠습니다...

도와주세요 ㅠㅠㅠ

#include<cstdio>

using namespace std;

long long arr[100001];
int num[100001];
long long max(long long a, long long b) {
	return a > b ? a : b;
}
long long pick(int start, int end) {

	if (start == end) return num[start]*num[start];

	int mid = (start + end) / 2;
	long long ans =max(pick(start, mid),pick(mid + 1, end));

	long long cand = num[mid]*num[mid];

	int first = mid;
	int last = mid;
	int h = num[mid];
	
	while (start <= first && last <= end) {
		int p = 0;
		int q = 0;
		if (first - 1 < start) p = -1;
		else p = num[first - 1];

		if (last + 1 > end) q = -1;
		else q = num[last + 1];

		if (p > q) {
			first--;
			if (h > p) h = p;
		}
		else {
			last++;
			if (h > q)h = q;
		}

		if (cand < h*(arr[last] - arr[first-1]))cand = h*(arr[last] - arr[first - 1]);
	}

	while (start < first) {
		first--;
		if (h > num[first])h = num[first];
		if (cand < h*(arr[last] - arr[first - 1]))cand = h*(arr[last] - arr[first - 1]);
	}
	while (last < end) {
		last++;
		if (h > num[last])h = num[last];
		if (cand < h*(arr[last] - arr[first - 1]))cand = h*(arr[last] - arr[first - 1]);
	}

	return max(cand, ans);
}

int main() {

	int n;
	scanf("%d", &n);
	arr[0] = 0;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &num[i]);
		arr[i] = arr[i - 1] + num[i];
	}

	printf("%lld", pick(1, n));
}

kb6912 6년 전 0

초기값 return 부분

if (start == end) return num[start]*num[start];

에서 num[start]*num[start] 값이 int 형 값 넘어가면 int형값 끼리 곱했기 떄문에 반환이 long long 값으로 안돼요

(long long)num[start]*num[start]로 하시면 될겁니다.

kimbregas 6년 전 0

알려주신대로 해도 39%에서 틀렸습니다.가 뜨네요 ㅠㅠㅠ

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

문제

문제

출처

ICPC

39%에서 계속 '틀렸습니다' 가 뜹니다ㅠㅠ 고수님들 도와주세여...

kimbregas 6년 전 0

kb6912 6년 전 0

kimbregas 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말