#754626 (PyPy3) No.1345 Beautiful BINGO

提出ソース

結果

問題	No.1345 Beautiful BINGO
ユーザー	👑 rin204
提出日時	2022-04-16 17:28:05
言語	PyPy3 (7.3.15)
結果	AC
実行時間	1,094 ms / 2,000 ms
コード長	2,336 bytes
コンパイル時間	890 ms
コンパイル使用メモリ	82,176 KB
実行使用メモリ	78,124 KB
最終ジャッジ日時	2024-12-25 21:17:46
合計ジャッジ時間	15,593 ms
ジャッジサーバーID （参考情報）	judge2 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	37 ms 52,864 KB
testcase_01	AC	39 ms 52,736 KB
testcase_02	AC	38 ms 52,608 KB
testcase_03	AC	40 ms 52,096 KB
testcase_04	AC	38 ms 52,268 KB
testcase_05	AC	56 ms 63,232 KB
testcase_06	AC	39 ms 52,480 KB
testcase_07	AC	98 ms 76,416 KB
testcase_08	AC	39 ms 52,224 KB
testcase_09	AC	35 ms 52,480 KB
testcase_10	AC	38 ms 52,992 KB
testcase_11	AC	40 ms 53,376 KB
testcase_12	AC	36 ms 52,608 KB
testcase_13	AC	88 ms 76,000 KB
testcase_14	AC	39 ms 52,608 KB
testcase_15	AC	39 ms 52,352 KB
testcase_16	AC	38 ms 53,760 KB
testcase_17	AC	38 ms 52,864 KB
testcase_18	AC	36 ms 52,608 KB
testcase_19	AC	36 ms 52,480 KB
testcase_20	AC	37 ms 52,864 KB
testcase_21	AC	37 ms 52,096 KB
testcase_22	AC	50 ms 62,848 KB
testcase_23	AC	53 ms 63,104 KB
testcase_24	AC	101 ms 76,196 KB
testcase_25	AC	151 ms 77,156 KB
testcase_26	AC	257 ms 77,184 KB
testcase_27	AC	1,027 ms 77,696 KB
testcase_28	AC	102 ms 76,168 KB
testcase_29	AC	255 ms 77,056 KB
testcase_30	AC	54 ms 65,408 KB
testcase_31	AC	115 ms 77,380 KB
testcase_32	AC	127 ms 77,620 KB
testcase_33	AC	1,035 ms 78,124 KB
testcase_34	AC	52 ms 65,792 KB
testcase_35	AC	71 ms 73,600 KB
testcase_36	AC	390 ms 77,056 KB
testcase_37	AC	47 ms 62,336 KB
testcase_38	AC	299 ms 77,528 KB
testcase_39	AC	1,009 ms 77,312 KB
testcase_40	AC	423 ms 77,616 KB
testcase_41	AC	392 ms 77,440 KB
testcase_42	AC	39 ms 52,328 KB
testcase_43	AC	35 ms 52,480 KB
testcase_44	AC	40 ms 52,608 KB
testcase_45	AC	39 ms 53,120 KB
testcase_46	AC	39 ms 52,352 KB
testcase_47	AC	39 ms 52,352 KB
testcase_48	AC	38 ms 52,864 KB
testcase_49	AC	39 ms 52,608 KB
testcase_50	AC	38 ms 52,480 KB
testcase_51	AC	38 ms 52,352 KB
testcase_52	AC	67 ms 69,632 KB
testcase_53	AC	1,029 ms 76,672 KB
testcase_54	AC	251 ms 77,316 KB
testcase_55	AC	403 ms 77,440 KB
testcase_56	AC	66 ms 69,504 KB
testcase_57	AC	1,028 ms 77,124 KB
testcase_58	AC	1,094 ms 77,312 KB
testcase_59	AC	1,015 ms 77,532 KB
testcase_60	AC	552 ms 77,696 KB
testcase_61	AC	559 ms 77,052 KB
testcase_62	AC	54 ms 64,512 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

def popcount(x):
    x = x - ((x >> 1) & 0x55555555)
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f
    x += x >> 8
    x += x >> 16
    return x & 0x0000003f

n, m = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(n)]

ans = 1 << 30
for bit in range(1 << n):
    pc = popcount(bit)
    if pc > m or pc + n < m:
        continue
    tmp = 0
    lst = [0] * n
    for i in range(n):
        if bit >> i & 1:
            for j in range(n):
                tmp += A[i][j]
        else:
            for j in range(n):
                lst[j] += A[i][j]
    lst.sort()
    tmp += sum(lst[:m - pc])
    ans = min(ans, tmp)
    
x = 0
for i in range(n):
    x += A[i][i]
    
for bit in range(1 << n):
    pc = popcount(bit) + 1
    if pc > m or pc + n < m:
        continue
    tmp = x
    lst = [0] * n
    for i in range(n):
        if bit >> i & 1:
            for j in range(n):
                if i != j:
                    tmp += A[i][j]
        else:
            for j in range(n):
                if i != j:
                    lst[j] += A[i][j]
    lst.sort()
    tmp += sum(lst[:m - pc])
    ans = min(ans, tmp)
    
    
x = 0
for i in range(n):
    x += A[i][n - 1 - i]
    
for bit in range(1 << n):
    pc = popcount(bit) + 1
    if pc > m or pc + n < m:
        continue
    tmp = x
    lst = [0] * n
    for i in range(n):
        if bit >> i & 1:
            for j in range(n):
                if i != n - 1 - j:
                    tmp += A[i][j]
        else:
            for j in range(n):
                if i != n - 1 - j:
                    lst[j] += A[i][j]
    lst.sort()
    tmp += sum(lst[:m - pc])
    ans = min(ans, tmp)


x = 0
for i in range(n):
    x += A[i][i]
    if i != n - 1 - i:
        x += A[i][n - 1 - i]
    
for bit in range(1 << n):
    pc = popcount(bit) + 2
    if pc > m or pc + n < m:
        continue
    tmp = x
    lst = [0] * n
    for i in range(n):
        if bit >> i & 1:
            for j in range(n):
                if i != n - 1 - j and i != j:
                    tmp += A[i][j]
        else:
            for j in range(n):
                if i != n - 1 - j and i != j:
                    lst[j] += A[i][j]
    lst.sort()
    tmp += sum(lst[:m - pc])
    ans = min(ans, tmp)

print(ans)

yukicoder

結果

テストケース

ソースコード