Submission #15463739


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[:], i8[:]), cache=True)
def f(X, P):
    INF = 10**18
    ind = np.argsort(X)
    X, P = X[ind], P[ind]
    N = len(X)
    if N == 0:
        return np.array([0], np.int64)
    # [0, i) から X[j] までのコストの和
    dp1 = np.zeros((N + 1, N), np.int64)
    for i in range(N):
        for j in range(N):
            dp1[i + 1, j] = np.abs(X[i] - X[j]) * P[i]
    for i in range(N):
        dp1[i + 1] += dp1[i]

    # [l, r]をひとまとめにするときのコストの最小値
    dp2 = np.empty((N, N), np.int64)
    for l in range(N):
        for r in range(l, N):
            dp2[l, r] = (dp1[r + 1] - dp1[l]).min()

    # [0,i] を j 件でとる場合のコストの最小値
    dp3 = np.full((N, N + 1), INF, np.int64)
    for i in range(N):
        dp3[i, 0] = np.sum(X[:i + 1] * P[:i + 1])
        dp3[i, 1] = dp2[0, i]
        for j in range(i):
            # [0,j] + (j,i]
            dp3[i, 1:] = np.minimum(dp3[i, 1:], dp3[j, :-1] + dp2[j + 1, i])
    return dp3[-1]

@njit((i8[:], i8[:]), cache=True)
def merge(A, B):
    LA, LB = len(A), len(B)
    INF = 10**18
    C = np.full(LA + LB - 1, INF, np.int64)
    for i in range(LA):
        C[i:i + LB] = np.minimum(C[i:i + LB], A[i] + B)
    return C

@njit((i8[:], ), cache=True)
def main(XYP):
    X, Y, P = XYP[::3], XYP[1::3], XYP[2::3]
    N = len(X)
    INF = 10**18
    ans = np.full(N + 1, INF, np.int64)
    full = (1 << N) - 1
    for x in range(1 << N):
        i_x = np.bool_([x & (1 << i) for i in range(N)])
        i_y = ~i_x
        dp = f(X[i_x & (X >= 0)], P[i_x & (X >= 0)])
        dp = merge(dp, f(-X[i_x & (X < 0)], P[i_x & (X < 0)]))
        dp = merge(dp, f(Y[i_y & (Y >= 0)], P[i_y & (Y >= 0)]))
        dp = merge(dp, f(-Y[i_y & (Y < 0)], P[i_y & (Y < 0)]))
        ans = np.minimum(ans, dp)
    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 2202 Byte
Status
Exec Time 1308 ms
Memory 111880 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 496 ms 111220 KB
00-sample-02.txt 495 ms 111876 KB
00-sample-03.txt 491 ms 110640 KB
01-corner-01.txt 1130 ms 111180 KB
01-corner-02.txt 1308 ms 111532 KB
01-corner-03.txt 1075 ms 111160 KB
01-corner-04.txt 503 ms 111124 KB
01-corner-05.txt 492 ms 111240 KB
02-random-01.txt 782 ms 111880 KB
02-random-02.txt 1071 ms 111140 KB
02-random-03.txt 1082 ms 111368 KB
02-random-04.txt 1082 ms 111500 KB
03-random-quarter-01.txt 859 ms 111868 KB
03-random-quarter-02.txt 1254 ms 111424 KB
03-random-quarter-03.txt 1288 ms 111168 KB
03-random-quarter-04.txt 1274 ms 111188 KB