Submission #25851789

Source Code Expand

import sys
import numpy as np
from numba import njit, i8

@njit((i8, i8, i8[:]), cache=True)
def main(N, K, A):
    A = A - 1
    popcnt = np.zeros(1 << K, np.int64)
    for i in range(K):
        popcnt[1 << i:1 << i + 1] = popcnt[:1 << i] + 1
    
    coef = np.zeros(K, np.int64)
    coef[:K//2] = -1
    coef[K-K//2:] = 1
    
    INF = 1 << 60
    DP = np.full(1 << K, INF, np.int64)
    DP[0] = 0
    for x in range(N):
        newDP = DP.copy()
        i = A[x]
        for s in range(1 << K):
            t = s | 1 << i
            if s == t:
                continue
            add_x = coef[popcnt[s]] * x
            add_inv = popcnt[s >> i]
            newDP[t] = min(newDP[t], DP[s] + add_x + add_inv)
        DP = newDP

    ANS = DP[-1]
    for x in range(K):
        ANS -= abs(K // 2 - x)
    return ANS

readline = sys.stdin.readline
N, K = map(int, readline().split())
A = np.array(readline().split(), np.int64)

print(main(N, K, A))

Submission Info

Submission Time
Task D - Pure Straight
User maspy
Language Python (3.8.2)
Score 600
Code Size 991 Byte
Status AC
Exec Time 504 ms
Memory 107636 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 69
Set Name Test Cases
Sample 01_sample_01.txt, 01_sample_02.txt, 01_sample_03.txt
All 01_sample_01.txt, 01_sample_02.txt, 01_sample_03.txt, 02_permutation_01.txt, 02_permutation_02.txt, 02_permutation_03.txt, 02_permutation_04.txt, 02_permutation_05.txt, 02_permutation_06.txt, 02_permutation_07.txt, 02_permutation_08.txt, 02_permutation_09.txt, 02_permutation_10.txt, 02_permutation_11.txt, 02_permutation_12.txt, 02_permutation_13.txt, 02_permutation_14.txt, 02_permutation_15.txt, 03_rand_01.txt, 03_rand_02.txt, 03_rand_03.txt, 03_rand_04.txt, 03_rand_05.txt, 03_rand_06.txt, 03_rand_07.txt, 03_rand_08.txt, 03_rand_09.txt, 03_rand_10.txt, 03_rand_11.txt, 03_rand_12.txt, 03_rand_13.txt, 03_rand_14.txt, 03_rand_15.txt, 03_rand_16.txt, 03_rand_17.txt, 03_rand_18.txt, 03_rand_19.txt, 03_rand_20.txt, 03_rand_21.txt, 03_rand_22.txt, 03_rand_23.txt, 03_rand_24.txt, 03_rand_25.txt, 03_rand_26.txt, 03_rand_27.txt, 03_rand_28.txt, 03_rand_29.txt, 03_rand_30.txt, 03_rand_31.txt, 03_rand_32.txt, 03_rand_33.txt, 04_large_ans_01.txt, 04_large_ans_02.txt, 04_large_ans_03.txt, 04_large_ans_04.txt, 04_large_ans_05.txt, 04_large_ans_06.txt, 04_large_ans_07.txt, 04_large_ans_08.txt, 04_large_ans_09.txt, 04_large_ans_10.txt, 04_large_ans_11.txt, 04_large_ans_12.txt, 05_partition_01.txt, 05_partition_02.txt, 05_partition_03.txt, 05_partition_04.txt, 05_partition_05.txt, 05_partition_06.txt
Case Name Status Exec Time Memory
01_sample_01.txt AC 500 ms 106356 KiB
01_sample_02.txt AC 473 ms 105448 KiB
01_sample_03.txt AC 479 ms 105452 KiB
02_permutation_01.txt AC 462 ms 105224 KiB
02_permutation_02.txt AC 468 ms 106384 KiB
02_permutation_03.txt AC 468 ms 105688 KiB
02_permutation_04.txt AC 469 ms 105592 KiB
02_permutation_05.txt AC 468 ms 106296 KiB
02_permutation_06.txt AC 469 ms 105716 KiB
02_permutation_07.txt AC 473 ms 106276 KiB
02_permutation_08.txt AC 465 ms 105716 KiB
02_permutation_09.txt AC 472 ms 105652 KiB
02_permutation_10.txt AC 464 ms 106204 KiB
02_permutation_11.txt AC 470 ms 105680 KiB
02_permutation_12.txt AC 467 ms 105884 KiB
02_permutation_13.txt AC 470 ms 105956 KiB
02_permutation_14.txt AC 476 ms 106288 KiB
02_permutation_15.txt AC 471 ms 106712 KiB
03_rand_01.txt AC 469 ms 105908 KiB
03_rand_02.txt AC 463 ms 106220 KiB
03_rand_03.txt AC 466 ms 105568 KiB
03_rand_04.txt AC 463 ms 106292 KiB
03_rand_05.txt AC 472 ms 106368 KiB
03_rand_06.txt AC 471 ms 106272 KiB
03_rand_07.txt AC 467 ms 105256 KiB
03_rand_08.txt AC 471 ms 105720 KiB
03_rand_09.txt AC 471 ms 105144 KiB
03_rand_10.txt AC 475 ms 105644 KiB
03_rand_11.txt AC 470 ms 105184 KiB
03_rand_12.txt AC 480 ms 105832 KiB
03_rand_13.txt AC 480 ms 106588 KiB
03_rand_14.txt AC 478 ms 106328 KiB
03_rand_15.txt AC 481 ms 105900 KiB
03_rand_16.txt AC 477 ms 106404 KiB
03_rand_17.txt AC 478 ms 106972 KiB
03_rand_18.txt AC 477 ms 106288 KiB
03_rand_19.txt AC 490 ms 105904 KiB
03_rand_20.txt AC 485 ms 106228 KiB
03_rand_21.txt AC 482 ms 106972 KiB
03_rand_22.txt AC 479 ms 106224 KiB
03_rand_23.txt AC 479 ms 106228 KiB
03_rand_24.txt AC 504 ms 107164 KiB
03_rand_25.txt AC 497 ms 107636 KiB
03_rand_26.txt AC 504 ms 107176 KiB
03_rand_27.txt AC 498 ms 106980 KiB
03_rand_28.txt AC 491 ms 106832 KiB
03_rand_29.txt AC 501 ms 107632 KiB
03_rand_30.txt AC 495 ms 106876 KiB
03_rand_31.txt AC 498 ms 107536 KiB
03_rand_32.txt AC 492 ms 106876 KiB
03_rand_33.txt AC 500 ms 106780 KiB
04_large_ans_01.txt AC 501 ms 107544 KiB
04_large_ans_02.txt AC 476 ms 106360 KiB
04_large_ans_03.txt AC 490 ms 107160 KiB
04_large_ans_04.txt AC 477 ms 107044 KiB
04_large_ans_05.txt AC 500 ms 106864 KiB
04_large_ans_06.txt AC 478 ms 106036 KiB
04_large_ans_07.txt AC 496 ms 106924 KiB
04_large_ans_08.txt AC 486 ms 106372 KiB
04_large_ans_09.txt AC 494 ms 106896 KiB
04_large_ans_10.txt AC 482 ms 105992 KiB
04_large_ans_11.txt AC 491 ms 107552 KiB
04_large_ans_12.txt AC 479 ms 107180 KiB
05_partition_01.txt AC 497 ms 106908 KiB
05_partition_02.txt AC 474 ms 106344 KiB
05_partition_03.txt AC 497 ms 106904 KiB
05_partition_04.txt AC 475 ms 107016 KiB
05_partition_05.txt AC 494 ms 107452 KiB
05_partition_06.txt AC 479 ms 106440 KiB