SERVS - Servers

Suppose we want to replicate a file over a collection of n servers, labeled S1, S2 ... Sn. To place a copy of the file at server Si results in a placement cost of ci, for an integer ci > 0. Now, if a user requests the file from server Si, and no copy of the file is present at Si, then the servers Si + 1, Si + 2, Si + 3 ... are searched in order until a copy of the file is finally found, say at server Sj, where j > i. This results in an access cost of ji. (Note that the lower-indexed servers Si−1, Si−2, ... are not consulted in this search.) The access cost is 0 if Si holds a copy of the file. We will require that a copy of the file be placed at server Sn, so that all such searches will terminate, at the latest, at Sn.

We’d like to place copies of the files at the servers so as to minimize the sum of placement and access costs. Formally, we say that a configuration is a choice, for each server Si with i = 1, 2 ... n−1, of whether to place a copy of the file at Si or not. (Recall that a copy is always placed at Sn.) The total cost of a configuration is the sum of all placement costs for servers with a copy of the file, plus the sum of all access costs associated with all n servers.

Write a program which reads from the standard input the placement costs and writes a single number, the minimum cost of a configuration. First line of the input consists of the number n of servers (1 ≤ n ≤ 1000). In the next n lines you are given the placement costs, in line i + 1 you are given the placement cost ci of server Si.

Example

Input:
4
1
1
1
9

Output:
12
Input:
4
4
3
2
1

Output:
6

Added by:Marek Adamczyk
Date:2013-11-28
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2024-03-23 05:18:23
Do divide and conquer on range of unassigned servers.
More testcases:
2
3 10
output:
11

10
5 10 1 2 4 9 8 6 4 9
output:
28
mask: 0010100001

10
8 5 7 4 3 1 3 4 1 5
output:
21
mask: 0001010011
2013-12-31 07:05:41 Ashwini
@groopy: its not 19th test case. even if your 1st test case output is wrong then also judge will run it till 19th test case.after that it checks for wrong answer. so just check your logic
2013-12-31 06:19:27 Ashwini
what are the constraints for ci?
2013-12-15 18:27:32 raunakrocks
AC!!

Last edit: 2013-12-30 12:57:47
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.