글 읽기 - 도무지 틀릴게 없어보여 질문드립니다

hoonww 4년 전 0

분할정복을 이용한 풀이입니다.

다른 질문글의 예제는 이미 다 테스트해봤습니다.

논리적으로 허점이 없어보이는데 틀린다고 해서 어디가 문제인지 너무 궁금합니다.

#include <stdio.h>
#define N 100005

int n;

typedef long long ll;

ll arr[N];

ll max(ll a, ll b)
{
	if(a>b) return a;
	return b;
}

ll f(int left, int right)
{
	if(left==right) return arr[left];
	int mid=(left+right)/2;
	ll ans=max(f(left, mid), f(mid+1, right));
	
	int a, b;
	a=mid;
	b=mid+1;
	ll top=arr[a]+arr[b]-max(arr[a], arr[b]);
	ans=max(ans, (b-a+1)*top);
	
	while(a>left || b<right){
		if((arr[a]>arr[b] && a!=left) || b==right){
			a--;
			top=top+arr[a]-max(top, arr[a]);
		}
		else{
			b++;
			top=top+arr[b]-max(top, arr[b]);
		}
		ans=max(ans, (b-a+1)*top);
	}
	
	return ans;
}

int main()
{
	
	int i;
	
	while(1){
		scanf("%d", &n);
		if(n==0) break;
		for(i=1; i<=n; i++)
			scanf("%lld", &arr[i]);
		
		printf("%lld\n", f(1, n));
	}
	
	return 0;
}

tlwpdus 4년 전 2

아래 데이터에서 답이 나오지 않습니다.

29번 줄에서 어떤 값을 비교해야 하는지 생각해보시면 도움이 될 것 같습니다.

4
1 4 3 3

hoonww 4년 전 0

아 논리상에 허점이 있었네요

좀 더 들여다보고 질문글올릴걸 후회하게 되네요 ㅠㅠ

tlwpdus님 도와주셔서 감사합니다!

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

문제

문제

출처

ICPC

도무지 틀릴게 없어보여 질문드립니다

hoonww 4년 전 0

tlwpdus 4년 전 2

hoonww 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말