Submission #17343567

---

Source Code Expand

import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8
import itertools

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

@njit((i8[:], i8[:], i8[:]), cache=True)
def f(L, W, A):
    N = len(A)
    X = np.zeros(N, np.int64)
    Acum = np.zeros(N + 1, np.int64)
    Acum[1:] = np.cumsum(A)
    for n in range(1, N):
        # n 人目を並べるとき。
        x = 0
        for i in range(n):
            # [i, n] の重さ
            wt = Acum[n + 1] - Acum[i]
            # その重さで破壊される橋の最大の長さ
            k = np.searchsorted(W, wt) - 1
            l = L[k]
            x = max(x, X[i] + l)
        X[n] = x
    return X[-1]

def main(N, A, LW, perms):
    L, W = LW[::2], LW[1::2]
    if W.min() < A.max():
        return -1
    INF = 1 << 60
    # 番兵
    L = np.append(L, 0)
    W = np.append(W, 0)
    L = np.append(L, INF)
    W = np.append(W, INF)
    # 重さ順に並べる
    argsort = W.argsort()
    L, W = L[argsort], W[argsort]
    # ある重さに対して、最も長いもの
    for i in range(len(L) - 1):
        L[i + 1] = max(L[i], L[i + 1])
    ans = INF
    for p in perms:
        x = f(L, W, A[p])
        ans = min(ans, x)
    return ans

N, M = map(int, readline().split())
perms = np.array(list(itertools.permutations(range(N))))
A = np.array(readline().split(), np.int64)
LW = np.array(read().split(), np.int64)

print(main(N, A, LW, perms))

Submission Info

Judge Result