BRKSTRNG - Breaking String

no tags 

A certain string-processing language allows the programmer to break a string into two pieces. Since this involves copying the old string, it costs n units of time to break a string of n characters into two pieces. Suppose a programmer wants to break a string into many pieces. The order in which the breaks are made can affect the total amount of time used. For example, suppose we wish to break a 20 character string after characters 3, 8, and 10 (numbering the characters in ascending order from the left-hand end, starting from 1). If the breaks are made in left-to-right order, then the first break cost 20 units of time, the second break costs 17 units of time, and the third breaks costs 12 units of time, a total of 49 units of time (see the sample below). If the breaks are made in right-to-left order, then the first break costs 20 units of time, the second break costs 10 units of time, and the third break costs 8 units of time, a total of 38 units of time.

The cost of making the breaks in left-to-right order:

thisisastringofchars     (original)
thi sisastringofchars    (cost: 20 units)
thi sisas tringofchars   (cost: 17 units)
thi sisas tr ingofchars  (cost: 12 units)
                         Total: 49 units.

The cost of making the breaks in right-to-left order:

thisisastringofchars     (original)
thisisastr ingofchars    (cost: 20 units)
thisisas tr ingofchars   (cost: 10 units)
thi sisas tr ingofchars  (cost:  8 units)
                         Total: 38 units.

Input

There are several test cases! In each test case, the first line contains 2 integers N (2 ≤ N ≤ 10000000) and M (1 ≤ M ≤ 1000, M < N). N is the original length of the string, and M is the number of the breaks. The following lines contain M integers Mi (1 ≤ Mi < N) in ascending order that represent the breaking positions from the string's left-hand end. Read input till EOF.

(There wont be more than 100 cases)

Output

For each test case, output in one line the least cost to make all the breakings.

Example

Input:
20 3
3 8 10
20 4
2 3 8 10

Output:
37
40


hide comments
johann_jpg: 2023-06-06 09:30:29

@prasoonjha1: Wrong answer on Test 4 has to do something with how you use the cin.eof(). the problem there is probably that the testcase contains another empty line or something. Just use an extra check after reading N and M. But still then the time limit is hard.

prasoonjha1: 2023-05-08 16:17:15

I am using knuth's optimization but continuously getting WA at test case 4....anyone got any hint?
Is it possible that any input in array would be equal to N.

Last edit: 2023-05-09 07:00:56
ahmed_57: 2022-11-13 19:51:30

knuth dp optimization

marethyu1: 2019-04-12 00:03:54

Knuth's optimization

kagami_taiga7: 2016-01-19 12:14:51

@mohit hahaha chutiya

mohit: 2016-01-19 12:11:17

nice question :)

Last edit: 2016-01-19 14:31:24
B S Sachin Govind: 2014-12-10 09:04:41

can u please explain how it is 37 ans of first case whil above it is explained as 38

Last edit: 2014-12-10 09:12:03
B S Sachin Govind: 2014-12-09 22:29:48

how to read till eof

--ans(Francky)--> http://lmgtfy.com/?q=c%2B%2B+eof

Last edit: 2014-12-10 00:51:55
Shafaet: 2013-11-26 13:16:49

@Shaka Shadows: Authors of faster solutions user priority queue, i am not sure how those solutions work, my solution is O(M^2).

Shaka Shadows: 2013-08-30 14:30:12

@Shafaet: Is it possible to solve this with a complexity better than O(M ^ 2)? My ACed solution has that complexity, but the running time is way worse than the other AC so far.


Added by:Shafaet
Date:2013-08-28
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Author: Wei, Qizheng, Source: ZOJ Monthly, June 2007