서프라이즈~
시간 제한1초메모리 제한512 MB
모든 연속 부분 배열을 인접한 두 개의 비어 있지 않은 구간으로 나눌 때 두 합의 차이를 최소로 하고, 그런 경우가 여러 개면 전체 합이 가장 큰 경우의 합을 구한다.
문제
쿠기는 가톨릭대학교 컴퓨터정보공학부 학부장이다. 곧 다가오는 시험 기간에 학생들에게 힘을 주고자 간식 행사에 안심 스테이크를 주려고 한다.
컴퓨터정보공학부에는 N명의 학생이 있고, 학생들은 1부터 N까지 고유한 학번이 부여되어 있다. 쿠기는 N명의 학생을 대상으로 스테이크를 몇 그램 먹고 싶은지 설문 조사를 했다. 설문 조사를 마치고 학생들의 설문 결과를 본 쿠기는 경악했다. 이 설문 조사 결과를 바탕으로 간식 행사를 진행한다면 다시는 간식 행사를 할 수 없다. 이미 간식 행사 홍보를 하여 주목을 받은 쿠기는 돌이킬 수 없어서 전부 다 주려고 했던 간식을 이벤트처럼 위장하려고 한다.
이벤트의 내용은 다음과 같다.
서프라이즈! 다음과 같은 조건을 만족하는 학생들에게 스테이크를 드려요!
1. 임의로 연속된 학번의 학생들을 정해요!
2. 임의로 대상 학생들을 두 그룹으로 나눠요! 대신 한 그룹의 학생들은 학번이 인접해야 해요! 그룹에는 최소 한 명의 학생이 있어야 해요!
3. 두 그룹의 스테이크 무게 합의 차 E를 구해요! E를 계산할 때는 합이 큰 그룹에서 작은 그룹의 합을 빼요!
4. 가능한 모든 경우에 대해 계산하여 E가 최솟값인 두 그룹의 학생들에게 스테이크를 드립니다!
5. 대신 최솟값이 같은 경우가 여러 가지라면 두 그룹의 스테이크 무게 합이 가장 큰 두 그룹의 학생들에게 스테이크를 드립니다!
예를 들면, 1번부터 6번 학생에 대한 설문 조사 결과가 [2, 1, 5, 2, 4, 4]일 때 다음과 같이 계산한다.
- 임의로 연속되게 학번이 2인 학생부터 6인 학생까지 정한다.
- 임의로 2번부터 3번 학생의 그룹과 4번부터 6번 학생의 그룹을 나눈다.
- 2번부터 3번 학생 그룹의 합은 6, 4번부터 6번 학생 그룹의 합은 10이므로 E는 4이다.
- 가능한 모든 경우에 대해 계산한다.
- 해당 예시에 대한 답은 2번부터 4번 학생 그룹과 5번부터 6번 학생 그룹일 때 E가 최소이므로 2번부터 6번 학생이 이벤트 당첨자다.
쿠기는 한시름 놨지만, 스테이크를 구매하기 위해 이벤트 당첨자들의 스테이크 무게의 합을 구하는 코드를 작성하려고 했는데 노트북이 망가졌다.
쿠기를 도와 당첨자들의 스테이크 무게 합을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정수 N(2 ≤ N ≤ 2,000)이 주어진다.
다음 줄에 1번 학생부터 N번 학생까지 차례대로 설문 조사에 적은 스테이크의 무게를 나타내는 정수 W(1 ≤ W ≤ 10,000)가 주어진다.
출력
이벤트에 당첨된 학생들의 스테이크 무게 합을 출력한다.