Submission #1001443


Source Code Expand

from math import sqrt
n = input()
P = [map(int, raw_input().split()) for i in xrange(n)]
A = [e[2] for e in P]

def dist(p, q):
    return sqrt((p[0] - q[0])**2 + (p[1] - q[1])**2)
que = []
for i in xrange(n):
    for j in xrange(i+1, n):
        que.append((dist(P[i], P[j]), i, j))
que.sort()

memo = [-1]*2**n
memo[0] = 0
def calc(state):
    if memo[state] != -1:
        return memo[state]
    res = 0
    cnt = 0
    for i in xrange(n):
        if (state >> i) & 1:
            res += A[i]
            cnt += 1
    parent = range(n)
    def root(x):
        if x != parent[x]:
            parent[x] = x = root(parent[x])
        return x
    def unite(x, y):
        px = root(x); py = root(y)
        if px < py:
            parent[py] = px
        else:
            parent[px] = py
    for d, i, j in que:
        if (state >> i) & 1 and (state >> j) & 1 and root(i) != root(j):
            unite(i, j)
            res -= d
    res /= float(cnt)
    memo[state] = res
    return res

dic = {}
for i in xrange(n):
    dic[1<<i] = A[i]
def dfs(state):
    if state in dic:
        return dic[state]

    res = calc(state)
    sub = (state - 1) & state
    while sub != 0:
        if sub <= sub ^ state:
            res = max(res, min(calc(sub ^ state), dfs(sub)))
        sub = (sub - 1) & state
    dic[state] = res
    return res
print "%.10f" % dfs(2**n-1)

Submission Info

Submission Time
Task E - Water Distribution
User yaketake08
Language PyPy2 (5.6.0)
Score 1000
Code Size 1425 Byte
Status AC
Exec Time 698 ms
Memory 64796 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1000 / 1000
Status
AC × 2
AC × 46
Set Name Test Cases
Sample example0.txt, example1.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, 043.txt, example0.txt, example1.txt
Case Name Status Exec Time Memory
000.txt AC 698 ms 64796 KB
001.txt AC 583 ms 53148 KB
002.txt AC 636 ms 56220 KB
003.txt AC 598 ms 55324 KB
004.txt AC 538 ms 47132 KB
005.txt AC 664 ms 54172 KB
006.txt AC 590 ms 55324 KB
007.txt AC 593 ms 50972 KB
008.txt AC 568 ms 55068 KB
009.txt AC 595 ms 50716 KB
010.txt AC 695 ms 55580 KB
011.txt AC 629 ms 54684 KB
012.txt AC 542 ms 50716 KB
013.txt AC 559 ms 53276 KB
014.txt AC 544 ms 50716 KB
015.txt AC 549 ms 52764 KB
016.txt AC 549 ms 50972 KB
017.txt AC 524 ms 49308 KB
018.txt AC 563 ms 53916 KB
019.txt AC 545 ms 51484 KB
020.txt AC 548 ms 52380 KB
021.txt AC 627 ms 58652 KB
022.txt AC 612 ms 57372 KB
023.txt AC 615 ms 56348 KB
024.txt AC 543 ms 51356 KB
025.txt AC 604 ms 54172 KB
026.txt AC 577 ms 53788 KB
027.txt AC 529 ms 49308 KB
028.txt AC 570 ms 52380 KB
029.txt AC 524 ms 48668 KB
030.txt AC 481 ms 45596 KB
031.txt AC 536 ms 50972 KB
032.txt AC 521 ms 51484 KB
033.txt AC 672 ms 53020 KB
034.txt AC 497 ms 50332 KB
035.txt AC 625 ms 49436 KB
036.txt AC 490 ms 47644 KB
037.txt AC 613 ms 50716 KB
038.txt AC 501 ms 47772 KB
039.txt AC 480 ms 47004 KB
040.txt AC 39 ms 8944 KB
041.txt AC 39 ms 8944 KB
042.txt AC 39 ms 8944 KB
043.txt AC 90 ms 14364 KB
example0.txt AC 39 ms 8944 KB
example1.txt AC 562 ms 50972 KB