oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

chocolate Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

chocolate.html

You have a huge block of chocolate of size 1xN. However, just as you are about to eat it, Kang the penguin comes along and demands that you share it with him! Thus, you begrudgingly decide to break the chocolate into two sets of pieces such that the total size of each set is N/2. However, it so happens that this block of chocolate is unnaturally hard at some points and unnaturally easy to break at some points. Thus, you want to ensure that you expend the minimum amount of effort to share your chocolate with the greedy penguin.

The chocolate can only be broken at whole number portions along its length, so as to preserve its taste. Given a1, a2, ... , aN-1, where ai represents the amount of effort needed to break the block of chocolate between piece i and piece i+1, output the minimum total effort required to create two sets of pieces of chocolate such that the total size of each one is N/2.

Input

The first line of the input consists of one even integer N (2 ≤ N ≤ 10,000).

The next N-1 lines of input contain one integer each, representing the values of ai in order (1 ≤ ai ≤ 10,000).

Output

Output one integer, the minimum total effort required

Sample Input 1

6
1
8
12
6
2

Sample Output 1

7

Explanation for Sample Output 1

Dividing the piece of chocolate between pieces 1 and 2, as well as between pieces 4 and 5 require 1+6=7 units of effort. Then, we keep pieces [1,1] and [5,6] for ourselves, while giving away [2,4] to the penguin. This is optimal.

Tags

Dynamic Programming

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
1100201s32MBAverage
2011s32MBAverage

Judge Compile Command

g++-8 ans.cpp -o chocolate -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.