Submission #17632953


Source Code Expand

Copy
"""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

Submission Time
Task E - Medals
User maspy
Language Python (3.8.2)
Score 700
Code Size 1704 Byte
Status AC
Exec Time 1899 ms
Memory 249932 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
AC × 3
AC × 40
Set Name Test Cases
Sample 00_sample_01, 00_sample_02, 00_sample_03
All 00_sample_01, 00_sample_02, 00_sample_03, 10_small_01, 10_small_02, 10_small_03, 10_small_04, 10_small_05, 10_small_06, 10_small_07, 10_small_08, 10_small_09, 10_small_10, 20_random_01, 20_random_02, 20_random_03, 20_random_04, 20_random_05, 20_random_06, 20_random_07, 20_random_08, 20_random_09, 20_random_10, 30_max_01, 30_max_02, 30_max_03, 30_max_04, 30_max_05, 31_max_01, 31_max_02, big_00, big_01, big_02, big_03, big_04, sml_00, sml_01, sml_02, sml_03, sml_04
Case Name Status Exec Time Memory
00_sample_01 AC 1899 ms 244600 KB
00_sample_02 AC 1276 ms 246292 KB
00_sample_03 AC 1120 ms 244468 KB
10_small_01 AC 1110 ms 244604 KB
10_small_02 AC 1118 ms 244504 KB
10_small_03 AC 1104 ms 244524 KB
10_small_04 AC 1118 ms 244676 KB
10_small_05 AC 1112 ms 245132 KB
10_small_06 AC 1113 ms 245344 KB
10_small_07 AC 1178 ms 244496 KB
10_small_08 AC 1202 ms 245468 KB
10_small_09 AC 1137 ms 244832 KB
10_small_10 AC 1168 ms 244776 KB
20_random_01 AC 1391 ms 245868 KB
20_random_02 AC 1387 ms 246896 KB
20_random_03 AC 1391 ms 245896 KB
20_random_04 AC 1111 ms 244648 KB
20_random_05 AC 1538 ms 249448 KB
20_random_06 AC 1151 ms 244832 KB
20_random_07 AC 1241 ms 246052 KB
20_random_08 AC 1113 ms 245164 KB
20_random_09 AC 1062 ms 245088 KB
20_random_10 AC 1359 ms 246860 KB
30_max_01 AC 1483 ms 247024 KB
30_max_02 AC 1586 ms 249252 KB
30_max_03 AC 1618 ms 249352 KB
30_max_04 AC 1490 ms 247868 KB
30_max_05 AC 1616 ms 249344 KB
31_max_01 AC 1626 ms 249356 KB
31_max_02 AC 1618 ms 249348 KB
big_00 AC 1496 ms 249204 KB
big_01 AC 1509 ms 249456 KB
big_02 AC 1530 ms 249160 KB
big_03 AC 1549 ms 249932 KB
big_04 AC 1536 ms 249136 KB
sml_00 AC 1208 ms 245276 KB
sml_01 AC 1183 ms 246180 KB
sml_02 AC 1209 ms 246020 KB
sml_03 AC 1207 ms 245624 KB
sml_04 AC 1198 ms 245544 KB