Submission #15448470


Source Code Expand

Copy
import sys
import numpy as np

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

def main(XYP):
    X, Y, P = XYP[::3], XYP[1::3], XYP[2::3]
    N = len(X)
    dp = np.empty((3**N, N), np.int64)  # 建設、人 -> コスト
    dp[0] = np.minimum(np.abs(X), np.abs(Y)) * P
    size = np.empty(3**N, np.int64)
    size[0] = 0
    for n in range(N):
        B = 3**n
        DX = np.abs(X - X[n]) * P
        DY = np.abs(Y - Y[n]) * P
        dp[B:2 * B] = np.minimum(dp[:B], DX)
        dp[2 * B:3 * B] = np.minimum(dp[:B], DY)
        size[B:2 * B] = size[:B] + 1
        size[2 * B:3 * B] = size[:B] + 1
    ans = np.full(N + 1, 10**18, np.int64)
    for s in range(3**N):
        n = size[s]
        ans[n] = min(ans[n], dp[s].sum())
    return ans

if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    i8 = numba.int64
    cc = CC('my_module')

    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return numba.njit(f)

    main = cc_export(main, (i8[:], ))
    cc.compile()

from my_module import main

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 0
Code Size 1295 Byte
Status
Exec Time 2849 ms
Memory 2326984 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0
All 0 / 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 115 ms 27096 KB
00-sample-02.txt 111 ms 27080 KB
00-sample-03.txt 115 ms 27324 KB
01-corner-01.txt 2849 ms 2326672 KB
01-corner-02.txt 2786 ms 2326640 KB
01-corner-03.txt 2825 ms 2326664 KB
01-corner-04.txt 112 ms 26844 KB
01-corner-05.txt 112 ms 27008 KB
02-random-01.txt 969 ms 756096 KB
02-random-02.txt 2791 ms 2326772 KB
02-random-03.txt 2814 ms 2326708 KB
02-random-04.txt 2807 ms 2326760 KB
03-random-quarter-01.txt 955 ms 755928 KB
03-random-quarter-02.txt 2809 ms 2326984 KB
03-random-quarter-03.txt 2786 ms 2326636 KB
03-random-quarter-04.txt 2846 ms 2326660 KB