Submission #1147698

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147698		mrariel	Coin Collecting (JOI19_ho_t4)	Pypy 3	0 / 100	151 ms	50868 KiB

joi2019_ho_t4

def min_total_moves(n, coins):
    targets = [(x, y) for x in range(1, n + 1) for y in range(1, 3)]
    coins.sort()
    targets.sort()
    
    cost = [[abs(cx - tx) + abs(cy - ty) for tx, ty in targets] for cx, cy in coins]
    
    dp = [float('inf')] * (3 ** (2 * n))
    dp[0] = 0
    
    for mask in range(3 ** (2 * n)):
        assigned = [0] * (2 * n)
        
        current_mask = mask
        for i in range(2 * n):
            assigned[i] = current_mask % 3
            current_mask //= 3
        
        x = sum(1 for i in range(2 * n) if assigned[i] != 0)
        if x >= 2 * n:
            continue
        
        for j in range(2 * n):
            if assigned[j] == 0:
                for new_target in range(1, 3):
                    new_mask = mask + (new_target * (3 ** j))
                    dp[new_mask] = min(dp[new_mask], dp[mask] + cost[x][j])
    
    return dp[-1]

if __name__ == "__main__":
    n = int(input())
    coins = [tuple(map(int, input().split())) for _ in range(2 * n)]
    print(min_total_moves(n, coins))

Compilation message (stdout)

Compiling 'joi2019_ho_t4.py'...

=======
  adding: __main__.pyc (deflated 47%)

=======

• Subtask 1: 0 / 8
• Subtask 2: 0 / 29
• Subtask 3: 0 / 63