글 읽기 - 왜 틀렸는지 모르겠어요 ..ㅠㅠ

pwr2011 4년 전 0

한번 봐주시면 정말로...

감사합니다 ㅠㅠㅠ

#include<iostream>
#include<algorithm>
#include<vector>
typedef long long ll;

using namespace std;

vector <ll> arr;

long long part_arr(long long s, long long e)
{
	if (s == e) //base case
		return arr[s] * arr[s];
	else if (1 + s == e) {//base case
		long long min_val = arr[s] < arr[e] ? arr[s] : arr[e];
		ll tmp = arr[s] * arr[s];
		tmp = arr[e] * arr[e] > tmp ? arr[e] * arr[e] : tmp;
		tmp = (arr[s] + arr[e]) * min_val > tmp ? (arr[s] + arr[e]) * min_val : tmp; // 이렇게 함으로써 tmp에 가장 큰 값이 들어가게 됨
		return tmp;
	}
	int mid = (s + e) / 2;
	ll max_candi = max(part_arr(s, mid), part_arr(mid , e));//mid를 걸치지 않은 정답을 가져옴. //ok

	int l = mid, r = mid;//mid를 걸치는 가장 큰 답을 찾아봄.
	int min_val = arr[mid];
	ll sum = arr[mid];
	ll max_answer = arr[mid];
	while (r - l+1< e - s) {
		ll p = l > s ? arr[l - 1] + sum : -1;
		ll q = r < e ? arr[r + 1] + sum : -1;

		if (p > q) {
			if (min_val > arr[l-1]) min_val = arr[l - 1];
			if (max_answer < p * min_val) {
				max_answer = p * min_val;
			}
				sum += arr[l - 1];
				l--;
			
		} 
		else {
			if (min_val > arr[r + 1]) min_val = arr[r + 1];
			if (max_answer < q * min_val) {
				max_answer = q * min_val;
			}
				sum += arr[r + 1];
				r++;
		}
	}
	if (max_answer < max_candi)
		max_answer = max_candi;
	return max_answer;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);


	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int tmp;
		cin >> tmp;
		arr.push_back(tmp);
	}  
	cout<<part_arr(0, n-1);
}

djm03178 4년 전 2

아래와 같은 입력일 때 arr의 범위를 벗어난 위치에 접근해서 값을 얻어내려고 하게 됩니다.

7
1 1 1 1 1 1 9

pwr2011 4년 전 0

정말 감사합니다 말씀해주신 부분에 관하여 수정을 좀 해봤습니다..! 그런데 이번에는 틀렸습니다가 나오네요...ㅜㅜㅜ

pwr2011 4년 전 0

r - l+1< e - s 이부분에서 -1을 빼니까 됬네요 ㅠ 감사합니다

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

문제

문제

출처

ICPC

왜 틀렸는지 모르겠어요 ..ㅠㅠ

pwr2011 4년 전 0

djm03178 4년 전 2

pwr2011 4년 전 0

pwr2011 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말