Submission #2474299


Source Code Expand

N = int(input())
S = []; T = []; R = []
for i in range(N):
    r, sx, sy, tx, ty = map(int, input().split())
    S.append((sx, sy))
    T.append((tx, ty))
    R.append(r)

def dot(s, t, u):
    sx, sy = s
    tx, ty = t
    ux, uy = u
    return (tx - sx)*(ux - sx) + (ty - sy)*(uy - sy)

def cross(s, t, u):
    sx, sy = s
    tx, ty = t
    ux, uy = u
    return (tx - sx)*(uy - sy) - (ux - sx)*(ty - sy)

def dist2(s, t):
    sx, sy = s
    tx, ty = t
    return (sx - tx)**2 + (sy - ty)**2

def check(r, s, t, r0, u):
    rr = (r + r0)**2
    if not dist2(s, u) > rr < dist2(t, u):
        return 1
    dd = dist2(s, t)
    if not 0 <= dot(s, t, u) <= dd:
        return 0
    if not (cross(s, t, u))**2 <= dd*rr:
        return 0
    return 1

memo = {0: 0}
def dfs(state):
    if state in memo:
        return memo[state]
    res = 0
    for i in range(N):
        if (state >> i) & 1 == 0:
            continue
        s = S[i]; t = T[i]; r = R[i]
        for j in range(N):
            if i == j:
                continue
            r0 = R[j]
            u = S[j] if (state >> j) & 1 else T[j]
            if check(r, s, t, r0, u):
                break
        else:
            res = max(res, dfs(state ^ (1 << i)) + 1)
    memo[state] = res
    return res
print(dfs(2**N - 1))

Submission Info

Submission Time
Task G - Coin Slider
User yaketake08
Language Python (3.4.3)
Score 0
Code Size 1344 Byte
Status TLE
Exec Time 2104 ms
Memory 3896 KB

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
AC × 25
TLE × 2
Set Name Test Cases
All 00_sample_00, 00_sample_01, 00_sample_02, 10_random_0, 10_random_1, 10_random_2, 10_random_3, 10_random_4, 10_random_5, 10_random_6, 10_random_7, 10_random_8, 10_random_9, 20_small_r_0, 20_small_r_1, 20_small_r_2, 20_small_r_3, 20_small_r_4, 20_small_r_5, 20_small_r_6, 20_small_r_7, 20_small_r_8, 20_small_r_9, 90_align_0, 91_star_0, 99_max_0, 99_max_1
Case Name Status Exec Time Memory
00_sample_00 AC 18 ms 3192 KB
00_sample_01 AC 18 ms 3192 KB
00_sample_02 AC 18 ms 3192 KB
10_random_0 AC 18 ms 3192 KB
10_random_1 AC 18 ms 3188 KB
10_random_2 AC 18 ms 3192 KB
10_random_3 AC 18 ms 3192 KB
10_random_4 AC 18 ms 3192 KB
10_random_5 AC 18 ms 3192 KB
10_random_6 AC 18 ms 3192 KB
10_random_7 AC 18 ms 3188 KB
10_random_8 AC 18 ms 3192 KB
10_random_9 AC 18 ms 3192 KB
20_small_r_0 AC 26 ms 3188 KB
20_small_r_1 AC 121 ms 3188 KB
20_small_r_2 AC 23 ms 3188 KB
20_small_r_3 AC 27 ms 3192 KB
20_small_r_4 AC 23 ms 3192 KB
20_small_r_5 AC 19 ms 3188 KB
20_small_r_6 AC 33 ms 3192 KB
20_small_r_7 AC 598 ms 3316 KB
20_small_r_8 AC 42 ms 3188 KB
20_small_r_9 AC 18 ms 3192 KB
90_align_0 AC 21 ms 3192 KB
91_star_0 AC 25 ms 3188 KB
99_max_0 TLE 2104 ms 3896 KB
99_max_1 TLE 2104 ms 3892 KB