Surprise~
Time limit1sMemory limit512 MB
Split every contiguous subarray into two adjacent nonempty parts, minimize the absolute sum difference, and among ties maximize the total sum.
- Level
Medium6 of 10
- Topics
- Prefix sum, Brute force, Array, Implementation
- Solved
- No attempts yet
Problem
Kuki is the head of the Department of Computer and Information Engineering at the Catholic University of Korea. With exams coming up, he wants to give the students a boost by serving tenderloin steak at a snack event.
The department has N students, each with a unique student ID from 1 to N. Kuki surveyed all N students to find out how many grams of steak each of them wants. After finishing the survey and reading the results, Kuki was horrified. If he runs the snack event based on these survey results, he will never be able to hold a snack event again. Since he has already publicized the event and drawn attention, he cannot back out, so he plans to disguise the snack he intended to give everyone as an event.
The event works as follows.
Surprise! We will give steak to the students who satisfy the following conditions!
1. Choose any consecutive range of student IDs!
2. Split the chosen students into two groups! However, the students in one group must have adjacent student IDs! Each group must contain at least one student!
3. Compute the difference E between the sums of steak weights of the two groups! When computing E, subtract the smaller group's sum from the larger group's sum!
4. We compute this for every possible case, and we give steak to the two groups whose E is the minimum!
5. However, if there are multiple cases with the same minimum, we give steak to the two groups whose combined steak weight sum is the largest!
For example, when the survey results for students 1 through 6 are [2, 1, 5, 2, 4, 4], the calculation goes as follows.
- Choose any consecutive range, say students 2 through 6.
- Split them into a group of students 2 through 3 and a group of students 4 through 6.
- The sum for students 2 through 3 is 6, and the sum for students 4 through 6 is 10, so E is 4.
- Compute this for every possible case.
- For this example, the answer is achieved by the group of students 2 through 4 and the group of students 5 through 6, since E is minimized there, so students 2 through 6 are the event winners.
Kuki was relieved, but when he tried to write code to compute the total steak weight of the event winners in order to buy the steaks, his laptop broke.
Help Kuki by writing a program that computes the total steak weight of the winners.
Input
The first line contains an integer N (2 ≤ N ≤ 2,000).
The next line contains N integers W (1 ≤ W ≤ 10,000), the steak weights from student 1 to student N in order, as written in the survey.
Output
Print the total steak weight of the students who won the event.