글 읽기 - 13%에서 틀렸습니다가 뜨는데 반례부탁드립니다.

hacastle 2년 전 0

안녕하세요.

13%에서 계속 틀렸습니다가 뜨는데 반례를 못찾겠습니다.

도움 주시면 감사하겠습니다.

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
long long arr[100001];

long long f(long long s, long long e)  
{
	if (s == e) return arr[s]*arr[s];  
	if (s + 1 == e) return max({arr[s]*arr[s], arr[e] * arr[e], (arr[e] + arr[s]) * min(arr[e], arr[s])});

	long long mid = (s + e) / 2;
	long long result = max(f(s, mid - 1), f(mid + 1, e));

	long long l = mid;
	long long r = mid;

	long long sum = arr[mid]; // sum : '합'을 저장.
	long long mini = arr[mid]; // mini : '최솟값'을 저장.
	int flag = 1;

	while ((l>s || r<e) && flag == 1) 
	{
		if (l > s) { 
			l--; //'왼쪽'으로
			if (sum * mini <= (sum + arr[l]) * (min(mini, arr[l])) && flag == 1) //왼쪽으로 갔는데 가능하다면 
			{
				mini = min(mini, arr[l]);
				sum += arr[l];
				continue;
			}
		}
		if (r < e) 
		{
			r++; //'오른쪽'으로
			if (sum * mini <= (sum + arr[r]) * (min(mini, arr[r])) && flag == 1) //오른쪽으로 갔는데 가능하다면
			{
				mini = min(mini, arr[r]);
				sum += arr[r];
				if (l != s) {  
					l++; //위에서 '왼쪽'추가가 불가능했어도, 오른쪽추가 이후에 다시하면 가능할 수도 있기 때문.
				}
				continue;
			}
			else flag = 0;
		}
	}
	return max(result, (sum * mini));
}

int main(void)
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++){
		cin >> arr[i];
	}
	if (n == 1) cout << arr[1] * arr[1]; 
	else cout << f(1, n);
	return 0;
}

hacastle 2년 전 0

자답합니다.

3 3 3 5 7 7 3 4 1

정답 105

오답 95

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

문제

문제

출처

ICPC

13%에서 틀렸습니다가 뜨는데 반례부탁드립니다.

hacastle 2년 전 0

hacastle 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말