forked from ynyeh0221/HackerRank
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Fair Cut.py
21 lines (20 loc) · 777 Bytes
/
Fair Cut.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
[n, k] = map(int, raw_input().split())
a = sorted(map(int, raw_input().split()))
T = [[-1 for j in xrange(n)] for i in xrange(n)]
for i in xrange(n):
if i == 0:
T[i][0] = 0
T[i][1] = 0
else:
for j in xrange(max(0,k-(n-i-1)), k+1):
if T[i-1][j] == -1:
continue
T[i][j] = T[i-1][j] + (a[i]-a[i-1])*j*(n-i-(k-j))
T[i][j] += (a[i]-a[i-1]) * (i-j) * (k-j)
for j in xrange(max(0,k-(n-i)), k):
if T[i-1][j] != -1:
if T[i][j+1] == -1:
T[i][j+1] = T[i-1][j] + (a[i]-a[i-1]) * (j*(n-i-(k-j))+(i-j)*(k-j))
else:
T[i][j+1] = min(T[i][j+1], T[i-1][j] + (a[i]-a[i-1])*(j*(n-i-(k-j))+(i-j)*(k-j)))
print T[n-1][k]