Problem:
Calender Colors Taro  is a member of a programming contest circle.
In this circle, the members manage their schedules in the system called Great Web Calender . Taro has just added some of his friends to his calendar so that he can browse their schedule on his calendar.
Then he noticed that the system currently displays all the schedules in only one color, mixing the schedules for all his friends.
This is  difficult to manage because  it's hard to tell whose schedule each entry is. But actually this calender system has the  feature to change  the color of schedule entries, based on the person who has the entries.
So Taro wants to  use that feature to distinguish their plans by color. Given the colors Taro can use and the number of members,
your task is to calculate the subset of colors to color all  schedule entries.
The colors are given by "Lab color space". In Lab color space,
the   distance between two colors is defined by the square sum of the difference of each element.
Taro has to pick up the  subset of colors  that maximizes the sum of distances of all color pairs in the set. Input The input is like the following style.  N  M  L_{0}  a_{0}  b_{0}  L_{1}  a_{1}  b_{1}  ...  L_{N-1}  a_{N-1}  b_{N-1}  The first line contains two integers N and M ( 0 \leq M \leq N \leq 20 ), where N is the number of colors in the input, and M is the number of friends Taro wants to select the colors for.
Each of the following N lines contains three decimal integers L ( 0.0 \leq L \leq 100.0 ), a ( -134.0 \leq a \leq 220.0 ) and b ( -140.0 \leq b \leq 122.0 ) which represents a single color in Lab color space. Output Output the maximal of the total distance.
The output should not contain an error greater than 10^{-5} . Sample Input 1 3 2
0 0 0
10 10 10
100 100 100 Output for the Sample Input 1 30000.00000000000000000000 Sample Input 2 5 3
12.0 15.0 9.0
10.0 -3.0 2.2
3.5 6.8 9.0
2.1 4.4 5.9
1.2 4.0 -5.4 Output for the Sample Input 2 1003.44000000000005456968 Sample Input 3 2 1
1.0 1.0 1.0
0.0 0.0 0.0 Output for the Sample Input 3 0.00000000000000000000

Solution (Python):
import itertools
N,M = map(int,raw_input().split())
lab = [map(float,raw_input().split()) for _ in range(N)]
ans = 0
for ele in itertools.combinations(lab,M):
    ans = max(ans,sum((ele[i][k]-ele[j][k])**2 for k in range(3) for i in range(M) for j in range(i+1,M)))
print "%.7f"%ans

Solution (Python):
from itertools import combinations
N,M = map(int,raw_input().split())
lab = [map(float,raw_input().split()) for _ in range(N)]
ans = max(sum((a[i]-b[i])**2 for i in range(3) for a,b in combinations(ele,2)) for ele in combinations(lab,M))
print "%.7f"%ans

Solution (Python):
from itertools import combinations
N,M = map(int,raw_input().split())
lab = [map(float,raw_input().split()) for _ in range(N)]
dist = [[sum((lab[i][k]-lab[j][k])**2 for k in range(3)) for i in range(N)] for j in range(N)]
print max(sum(dist[i][j] for i,j in combinations(ele,2)) for ele in combinations(range(N),M))

Solution (Python):
from itertools import combinations as comb
def cube_dist(a,b):
	return sum([(a[i]-b[i])**2 for i in range(3)])
def cal_total_dist(t):
	if len(t) == 1:
		return 0
	return sum([cube_dist(ca,cb) for ca, cb in comb(t,2)])

N, M = map(int,raw_input().split())
color = [tuple(map(float,raw_input().split())) for i in range(N)]
print max([cal_total_dist(ctuple) for ctuple in comb(color,M)])

Solution (Python):
from itertools import combinations as comb
def cube_dist(a,b):
	return sum([(a[i]-b[i])**2 for i in range(3)])
def cal_total_dist(t,dist_d):
	if len(t) == 1:
		return 0
	return sum([dist_d[(ca,cb)] for ca, cb in comb(t,2)])

N, M = map(int,raw_input().split())
color = [tuple(map(float,raw_input().split())) for i in range(N)]
cube_dist_dict = dict()
for a,b in comb(color,2):
	cube_dist_dict[(a,b)] = cube_dist(a,b)
print max([cal_total_dist(ctuple, cube_dist_dict) for ctuple in comb(color,M)])

Solution (Python):


import itertools

N, M = map(int, raw_input().split())
c = []
for i in xrange(N):
    c.append(map(float, raw_input().split()))

d = [[0]*N for i in range(N)]
for i in xrange(N):
    for j in xrange(i+1, N):
        L2 = (c[i][0]-c[j][0])**2
        a2 = (c[i][1]-c[j][1])**2
        b2 = (c[i][2]-c[j][2])**2
        d[i][j] = d[j][i] = L2+a2+b2
mdis = 0
for com in list(itertools.combinations(range(N), M)):
    dis = 0
    for i, j in list(itertools.combinations(com, 2)):
        dis += d[i][j]
    if mdis < dis: mdis=dis
print mdis

Solution (Python):
import itertools as itr

n, m = map(int, input().split())
a = [list(map(float, input().split())) for i in range(n)]
ans = 0
for p in itr.combinations(a, m):
    sm = 0
    for i in range(m):
        for j in range(i + 1, m):
            for k in range(3):
                sm += (p[i][k] - p[j][k]) ** 2
    ans = max(ans, sm)
print(ans)

Solution (Python):
import itertools
N,M = map(int,input().split())
src = [tuple(map(float,input().split())) for i in range(N)]
if M <= 1:
    print(0)
    exit()
dists = [[None for j in range(N)] for i in range(N)]
for i in range(N-1):
    for j in range(i+1,N):
        l1,a1,b1 = src[i]
        l2,a2,b2 = src[j]
        dist = 0
        dist += (l1-l2)**2 + (a1-a2)**2 + (b1-b2)**2
        dists[i][j] = dists[j][i] = dist

ans = 0
for ptn in list(itertools.combinations(range(N),M)):
    total = 0
    for i in range(M-1):
        for j in range(i+1,M):
            total += dists[ptn[i]][ptn[j]]
    ans = max(ans, total)
print(ans)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []
    ii = [2**i for i in range(21)]

    def f(a,b):
        r = 0
        for i in range(3):
            r += (a[i]-b[i]) ** 2
        return r

    while True:
        n,m = LI()
        a = [LF() for _ in range(n)]
        sa = [[0]*n for _ in range(n)]
        for i in range(n):
            for j in range(i+1,n):
                sa[i][j] = f(a[i],a[j])

        r = 0
        for i in range(2**n):
            t = [_ for _ in range(n) if i&ii[_]]
            if len(t) != m:
                continue
            tr = 0
            for i in range(m):
                for j in range(i+1,m):
                    tr += sa[t[i]][t[j]]
            if r < tr:
                r = tr

        rr.append(r)
        break

    return '\n'.join(map(str, rr))


print(main())

Solution (Python):
import itertools

memo = {}

def dist(x, y):
    key = (x, y)
    if key in memo:
        return memo[key]
    
    v = sum(map(lambda x: (x[0] - x[1]) ** 2, zip(x, y)))
    memo[key] = v
    return v


N, M = map(int, raw_input().split())
color = []
for i in xrange(N):
    l, a, b = map(float, raw_input().split())
    color.append((l, a, b))

m = -1
for c in itertools.combinations(color, M):
    temp = 0
    for i in xrange(M - 1):
        for j in xrange(i + 1, M):
            temp += dist(c[i], c[j])

    m = max(m, temp)

print '{:.10f}'.format(m)

Solution (Python):
from itertools import combinations
def dist(a, b):
	return sum((x - y) ** 2 for x, y in zip(a, b))
n, m = map(int, raw_input().split())
colors = [tuple(map(float, raw_input().split())) for i in xrange(n)]
dists = [[ dist(colors[i], colors[j]) for j in xrange(n)] for i in xrange(n)]
print max([sum(dists[a][b] for a, b in combinations(selected, 2)) for selected in combinations(xrange(n), m)])

Solution (Python):
import itertools
N,M=map(int,raw_input().split())
data=[map(float,raw_input().split()) for i in range(N)]
maxV=0.0
for comb in itertools.combinations(range(N),M):
    dist=0.0
    for i in range(M-1):
        for j in range(i+1,M):
            t=comb[i]
            s=comb[j]
            dist+=pow(data[t][0]-data[s][0],2)+pow(data[t][1]-data[s][1],2)+pow\
(data[t][2]-data[s][2],2)
    maxV=max(maxV,dist)
print maxV

Solution (Python):
def main():
    n, m = map(int, input().split())
    import itertools
    full = itertools.combinations(range(n), m)
    l = [list(map(float, input().split())) for i in range(n)]
    
    differ = [[0] * n for _ in range(n)]
    for i in range(n):
        for k in range(i + 1, n):
            tmp = 0
            for j in range(3):
                tmp += (l[i][j] - l[k][j]) ** 2
                
            differ[i][k] = tmp
            differ[k][i] = tmp
    
    ans = 0
    for f in full:
        tmp = 0
        f = list(f)
        for f1i in range(len(f)):
            for f2i in range(f1i + 1, len(f)):
                tmp += differ[f[f1i]][f[f2i]]
                
        ans = max(ans, tmp)
    print(ans)



if __name__ == "__main__":
    main()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m = LI()
    p = [[float(x) for x in input().split()] for i in range(n)]
    f = [[sum([(a-b)**2 for (a,b) in zip(p[i],p[j])]) for j in range(n)] for i in range(n)]
    l = 1<<n
    ans = 0
    for b in range(l):
        if bin(b).count("1") != m:
            continue
        s = 0
        for i in range(n):
            if not b&(1<<i):
                continue
            x = p[i]
            for j in range(i):
                if not b&(1<<j):
                    continue
                y = p[j]
                s += f[i][j]
        if ans < s:
            ans = s
    print(ans)
    return


if __name__ == "__main__":
    solve()