BRKSTRNG  Breaking String
A certain stringprocessing 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 lefthand end, starting from 1). If the breaks are made in lefttoright 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 righttoleft 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 lefttoright 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 righttoleft 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 lefthand 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.
Sample Input:
20 3
3 8 10
20 4
2 3 8 10
Sample Output:
37
40
hide comments
marethyu1:
20190412 00:03:54
Knuth's optimization 

kagami_taiga7:
20160119 12:14:51
@mohit hahaha chutiya 

mohit:
20160119 12:11:17
nice question :) Last edit: 20160119 14:31:24 

B S Sachin Govind:
20141210 09:04:41
can u please explain how it is 37 ans of first case whil above it is explained as 38 Last edit: 20141210 09:12:03 

B S Sachin Govind:
20141209 22:29:48
how to read till eof


Shafaet:
20131126 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:
20130830 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. 

J.A.R.V.I.S.:
20130829 14:31:35
clrs problem 
Added by:  Shafaet 
Date:  20130828 
Time limit:  1s2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Author: Wei, Qizheng, Source: ZOJ Monthly, June 2007 