Submission #17632953

---

Source Code Expand

"""TLE?"""
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

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

MAX = 1 << 24

def from_read(dtype=np.int64):
    return np.fromstring(read().decode(), dtype=dtype, sep=' ')


def from_readline(dtype=np.int64):
    return np.fromstring(readline().decode(), dtype=dtype, sep=' ')

@njit
def precompute(A):
    N = len(A)
    dp = np.zeros(MAX, np.int64)
    for i in range(N):
        a = A[i]
        mod = 0
        for d in range(MAX):
            # d 日目の状況
            if mod < a:
                dp[d] |= 1 << i
            mod += 1
            if mod >= a + a:
                mod -= a + a
    popcount = np.zeros(1 << N, np.int64)
    for n in range(1 << N):
        popcount[n] = popcount[n // 2] + (n % 2)
    return dp, popcount

@njit
def test(A, popcount, K, D):
    # D 日間集計して、Hall conditionを満たすかどうか確認する
    full = (1 << N) - 1
    dp = np.zeros(1 << N, np.int64)
    for d in range(D):
        s = A[d]
        dp[full ^ s] += 1
    # subset zeta
    for n in range(N):
        for s in range(1 << N):
            t = s ^ 1 << n
            if s < t:
                continue
            dp[t] += dp[s]
    return np.all((D - dp - popcount * K) >= 0)

def main(A, K):
    B, popcount = precompute(A)
    l, r = 0, MAX
    while l + 1 < r:
        x = (l + r) // 2
        if test(B, popcount, K, x):
            r = x
        else:
            l = x
    return r

N, K = map(int, readline().split())
A = from_readline()

print(main(A, K))

Submission Info

Judge Result