Submission #15454058


Source Code Expand

Copy
import sys
import numpy as np
import numba
from numba import njit
i8 = numba.int64

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8[:], ), cache=True)
def main(XYP):
    X, Y, P = XYP[::3], XYP[1::3], XYP[2::3]
    N = len(X)
    dp_X = np.empty((1 << N, N), np.int64)  # 建設、人 -> Xコスト
    dp_X[0] = np.abs(X) * P
    for n in range(N):
        B = 1 << n
        dp_X[B:2 * B] = np.minimum(dp_X[:B], np.abs(X - X[n]) * P)

    dp_Y = np.empty((1 << N, N), np.int64)  # 建設、人 -> Xコスト
    dp_Y[0] = np.abs(Y) * P
    for n in range(N):
        B = 1 << n
        dp_Y[B:2 * B] = np.minimum(dp_Y[:B], np.abs(Y - Y[n]) * P)

    popcount = np.zeros(1 << N, np.int64)
    for n in range(N):
        popcount[1 << n:1 << n + 1] = popcount[:1 << n] + 1

    INF = 10**18
    ans = np.full(N + 1, INF, np.int64)
    for s in range(1 << N):
        size = popcount[s]
        t = s
        while True:
            u = s ^ t
            cost = (np.minimum(dp_X[t], dp_Y[u])).sum()
            ans[size] = min(ans[size], cost)
            if t == 0:
                break
            t = (t - 1) & s
    return ans

N = int(readline())
XYP = np.array(read().split(), np.int64)

ans = main(XYP)
print('\n'.join(map(str, ans.tolist())))

Submission Info

Submission Time
Task E - M's Solution
User maspy
Language Python (3.8.2)
Score 500
Code Size 1366 Byte
Status
Exec Time 2256 ms
Memory 117544 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0
All 500 / 500 00-sample-01.txt, 00-sample-02.txt, 00-sample-03.txt, 01-corner-01.txt, 01-corner-02.txt, 01-corner-03.txt, 01-corner-04.txt, 01-corner-05.txt, 02-random-01.txt, 02-random-02.txt, 02-random-03.txt, 02-random-04.txt, 03-random-quarter-01.txt, 03-random-quarter-02.txt, 03-random-quarter-03.txt, 03-random-quarter-04.txt
Case Name Status Exec Time Memory
00-sample-01.txt 531 ms 107284 KB
00-sample-02.txt 516 ms 107948 KB
00-sample-03.txt 514 ms 107280 KB
01-corner-01.txt 1985 ms 116848 KB
01-corner-02.txt 2011 ms 116880 KB
01-corner-03.txt 2256 ms 116884 KB
01-corner-04.txt 561 ms 107276 KB
01-corner-05.txt 551 ms 107976 KB
02-random-01.txt 1025 ms 112440 KB
02-random-02.txt 2083 ms 117544 KB
02-random-03.txt 2028 ms 117544 KB
02-random-04.txt 2021 ms 116860 KB
03-random-quarter-01.txt 1055 ms 111624 KB
03-random-quarter-02.txt 2034 ms 117156 KB
03-random-quarter-03.txt 2027 ms 116884 KB
03-random-quarter-04.txt 2053 ms 116888 KB