Submission #48410397

---

Source Code Expand

import os
import sys
import heapq

sys.setrecursionlimit(210000)


if os.getenv('TEST'):
    def eprint(*args, **kwargs):
        print('[\033[31mEPRINT\033[0m]', *args, file=sys.stderr, **kwargs)
else:
    def eprint(*args, **kwargs):
        pass


def main() -> None:
    N, D = map(int, input().split())
    weights = list(map(int, input().split()))
    avg = sum(weights) / D

    packs = [0] * (1 << N)
    for i in range(1 << N):
        for n in range(N):
            if i & (1 << n) != 0:
                packs[i] += weights[n]

    vars = [[float('inf')] * (1 << N) for _ in range(D)]
    for i in range(1 << N):
        vars[0][i] = (packs[i] - avg)**2

    for i in range(1, D):
        for j in range(1 << N):
            k = j
            while True:
                vars[i][j] = min(vars[i][j], vars[i - 1][j ^ k] + vars[0][k])
                if k == 0:
                    break
                k = (k - 1) & j

    for var in vars:
        eprint(', '.join(f'{v:.1f}' for v in var))

    print(vars[-1][-1] / D)


if __name__ == '__main__':
    main()

Submission Info

Judge Result