NOI '10 P2 - Super Piano - DMOJ: Modern Online Judge

NOI '10 P2 - Super Piano

View as PDF

Submit solution

All submissions

Best submissions

Points: 25 (partial)

Time limit: 1.0s

Memory limit: 512M

Problem type

National Olympiad in Informatics, China, 2010

Little Z is a minorly famous pianist. Recently, Doctor C has gifted him with a super piano. With it, little Z hopes to create the world's most enchanting music.

The super piano has $n$ $n$ different keys in a row, numbered from $1$ $1$ to $n$ $n$ . The value of the $i$ $i$ -th key is $A_i$ $A_{i}$ , where $A_i$ $A_{i}$ can be positive or negative.

A chord consists of a sequence of between $L$ $L$ and $R$ $R$ consecutive keys. Two chords are considered the same if they contain the same sequence of notes.

We define the value of a chord as the sum of the values of all its notes.

Little Z decides to compose a piece consisting of $k$ $k$ different chords. Note that the chords are independent, so may overlap. Find the maximum sum of values of these chords.

Input Specification

The first line contains four positive integers $n$ $n$ , $k$ $k$ , $L$ $L$ , and $R$ $R$ . $n$ $n$ represents the number of keys on the super piano. $k$ $k$ represents the number of different chords that the piece should consist of. $L$ $L$ and $R$ $R$ respectively represent the minimum and maximum number of keys that can be in a single chord.

The next $n$ $n$ lines each contain one integer, with the $i$ $i$ -th line containing $A_i$ $A_{i}$ .

Output Specification

The output consists of a single integer, the maximum possible value of a piece that little Z can compose.

Sample Input

Copy

Sample Output

Copy

Explanation

There are $5$ $5$ possible super chords:

Notes $1$ $1$ to $2$ $2$ , for a total value of $3 + 2 = 5$ $3 + 2 = 5$
Notes $2$ $2$ to $3$ $3$ , for a total value of $2 + (-6) = -4$ $2 + (- 6) = - 4$
Notes $3$ $3$ to $4$ $4$ , for a total value of $(-6) + 8 = 2$ $(- 6) + 8 = 2$
Notes $1$ $1$ to $3$ $3$ , for a total value of $3 + 2 + (-6) = -1$ $3 + 2 + (- 6) = - 1$
Notes $2$ $2$ to $4$ $4$ , for a total value of $2 + (-6) + 8 = 4$ $2 + (- 6) + 8 = 4$

The maximum value chords are $1$ $1$ , $3$ $3$ , and $5$ $5$ , for a total of $5 + 2 + 4 = 11$ $5 + 2 + 4 = 11$ .

Constraints

There are $10$ $10$ total test cases with bounds satisfying:

Test Case	$N$ $N$	$k$ $k$
$1$ $1$	$\le 10$ $\leq 10$	$\le 100$ $\leq 100$
$2$ $2$	$\le 1\,000$ $\leq 1 000$	$\le 500\,000$ $\leq 500 000$
$3$ $3$	$\le 100\,000$ $\leq 100 000$	$= 1$ $= 1$
$4$ $4$	$\le 10\,000$ $\leq 10 000$	$\le 10\,000$ $\leq 10 000$
$5$ $5$	$\le 500\,000$ $\leq 500 000$	$\le 10\,000$ $\leq 10 000$
$6$ $6$	$\le 80\,000$ $\leq 80 000$	$\le 80\,000$ $\leq 80 000$
$7$ $7$	$\le 100\,000$ $\leq 100 000$	$\le 100\,000$ $\leq 100 000$
$8$ $8$	$\le 100\,000$ $\leq 100 000$	$\le 500\,000$ $\leq 500 000$
$9$ $9$	$\le 500\,000$ $\leq 500 000$	$\le 500\,000$ $\leq 500 000$
$10$ $10$	$\le 500\,000$ $\leq 500 000$	$\le 500\,000$ $\leq 500 000$

All of the test cases satisfy $-1000 \le A_i \le 1000$ $- 1000 \leq A_{i} \leq 1000$ and $1 \le L \le R \le n$ $1 \leq L \leq R \leq n$ .
Furthermore, it is guaranteed that a composition fitting the requirements will exist.

Problem translated to English by Alex, editted by rpeng.

Comments

There are no comments at the moment.