Submission #17343567


Source Code Expand

Copy
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

Submission Time
Task C - Camels and Bridge
User maspy
Language Python (3.8.2)
Score 500
Code Size 1553 Byte
Status
Exec Time 772 ms
Memory 122368 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
× 4
× 64
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
All ng_01.txt, ng_02.txt, ng_03.txt, ng_04.txt, ng_05.txt, ng_06.txt, ng_07.txt, ng_08.txt, ng_09.txt, ng_10.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, random_29.txt, random_30.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, small_01.txt, small_02.txt, small_03.txt, small_04.txt, small_05.txt, small_06.txt, small_07.txt, small_08.txt, small_09.txt, small_10.txt, small_11.txt, small_12.txt, small_13.txt, small_14.txt, small_15.txt, small_16.txt, small_17.txt, small_18.txt, small_19.txt, small_20.txt
Case Name Status Exec Time Memory
ng_01.txt 634 ms 121512 KB
ng_02.txt 609 ms 122048 KB
ng_03.txt 615 ms 121336 KB
ng_04.txt 613 ms 121412 KB
ng_05.txt 603 ms 121244 KB
ng_06.txt 589 ms 113140 KB
ng_07.txt 579 ms 113360 KB
ng_08.txt 580 ms 113740 KB
ng_09.txt 578 ms 113748 KB
ng_10.txt 573 ms 112696 KB
random_01.txt 752 ms 122368 KB
random_02.txt 770 ms 122140 KB
random_03.txt 743 ms 121252 KB
random_04.txt 757 ms 122068 KB
random_05.txt 752 ms 121420 KB
random_06.txt 768 ms 121348 KB
random_07.txt 750 ms 122144 KB
random_08.txt 754 ms 120844 KB
random_09.txt 749 ms 121352 KB
random_10.txt 772 ms 122132 KB
random_11.txt 665 ms 113084 KB
random_12.txt 662 ms 113720 KB
random_13.txt 670 ms 113112 KB
random_14.txt 649 ms 113744 KB
random_15.txt 664 ms 112596 KB
random_16.txt 663 ms 113744 KB
random_17.txt 664 ms 112576 KB
random_18.txt 658 ms 113316 KB
random_19.txt 660 ms 112700 KB
random_20.txt 661 ms 113888 KB
random_21.txt 528 ms 105976 KB
random_22.txt 548 ms 107612 KB
random_23.txt 553 ms 106676 KB
random_24.txt 542 ms 106572 KB
random_25.txt 534 ms 106960 KB
random_26.txt 547 ms 106828 KB
random_27.txt 545 ms 106920 KB
random_28.txt 531 ms 106772 KB
random_29.txt 530 ms 105964 KB
random_30.txt 531 ms 106764 KB
sample_01.txt 524 ms 106088 KB
sample_02.txt 505 ms 105604 KB
sample_03.txt 629 ms 113344 KB
sample_04.txt 635 ms 113104 KB
small_01.txt 643 ms 113164 KB
small_02.txt 661 ms 113324 KB
small_03.txt 644 ms 113892 KB
small_04.txt 642 ms 113272 KB
small_05.txt 654 ms 113744 KB
small_06.txt 653 ms 113376 KB
small_07.txt 651 ms 112700 KB
small_08.txt 661 ms 113160 KB
small_09.txt 653 ms 112644 KB
small_10.txt 659 ms 113076 KB
small_11.txt 654 ms 113156 KB
small_12.txt 652 ms 113068 KB
small_13.txt 657 ms 113156 KB
small_14.txt 641 ms 112996 KB
small_15.txt 655 ms 113720 KB
small_16.txt 661 ms 113200 KB
small_17.txt 654 ms 112704 KB
small_18.txt 659 ms 112724 KB
small_19.txt 660 ms 113084 KB
small_20.txt 660 ms 113000 KB