An archive stores n record keys already in sorted order. Key i (1-indexed by position) is looked up f[i] times per day. You arrange the keys into a binary search tree: an in-order traversal of the tree must visit the keys in their given sorted order (so the tree's structure is a valid BST over these keys).
Looking up a key costs one comparison per node visited from the root down to it, i.e. its depth counting the root as depth 1. The daily search cost of a tree is the sum over all keys of f[i] times the depth of key i. Build the tree that minimizes this total, and report the minimum daily search cost.
Line 1: an integer n, the number of keys.
Line 2: n space-separated positive integers, the access frequencies in sorted-key order.
A single integer: the minimum total weighted search cost.
Example 1
Input
3 34 8 50
Expected
142
Explanation
Making the third key (frequency 50) the root, with the first two keys forming its left subtree arranged best, yields a minimum daily cost of 142.
Example 2
Input
1 5
Expected
5
Explanation
A single key sits at the root at depth 1, so the cost is 5*1 = 5.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →