Mock CCO '18 Contest 1 Problem 6 - A Combining Problem - Olympiads Online Judge

Mock CCO '18 Contest 1 Problem 6 - A Combining Problem

View as PDF

Submit solution

All submissions

Best submissions

Points: 15 (partial)

Time limit: 0.3s

Memory limit: 16M

Problem type

Given a list of $N$ $N$ integers, we can take two adjacent integers, remove both of them, and insert the larger of the two where the two integers originally were. This incurs cost equal to the larger of the two integers. Compute the minimum cost needed to reduce this list to having just one integer.

Constraints

$1 \le N \le 10^6$ $1 \leq N \leq 10^{6}$

$0 \le a_i \le 10^9$ $0 \leq a_{i} \leq 10^{9}$

For at most 30% of marks, $N \le 500$ $N \leq 500$ .

For at most 50% of marks, $N \le 20\,000$ $N \leq 20 000$ .

Input Specification

The first line will contain a single integer, $N$ $N$ .

Each of the next $N$ $N$ lines will contain an integer $a_i$ $a_{i}$ , the integers of the list in order.

Output Specification

Output the minimum cost.

Sample Input

Copy

Sample Output

Copy

Comments

-4

p1geon commented on Jan. 5, 2020, 3:17 a.m. ← edited →

Wouldn't the second constraint be better written as $\displaystyle 2 \cdot 10^4$ $2 \cdot 10^{4}$