結果

問題 No.2520 L1 Explosion
ユーザー MasKoaTS
提出日時 2022-01-30 15:42:48
言語 PyPy3
(7.3.15)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 857 bytes
コンパイル時間 591 ms
コンパイル使用メモリ 82,332 KB
実行使用メモリ 158,104 KB
最終ジャッジ日時 2024-09-24 19:37:28
合計ジャッジ時間 4,077 ms
ジャッジサーバーID
(参考情報)
judge4 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample WA * 2 RE * 1
other WA * 2 RE * 1 TLE * 1 -- * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import sys
input = sys.stdin.readline
INF = 10 ** 18
N, K = map(int, input().split())
P = [list(map(int, input().split())) for _ in [0] * N]
def calc(bit):
x = []; y = []
i = 0
while(bit):
if(bit & 1):
x.append((P[i][0] + P[i][1], i))
y.append((P[i][0] - P[i][1], i))
bit >>= 1
i += 1
if(len(x) == 0):
return 0
x.sort(); y.sort()
p = x[0][1]; q = x[-1][1]
if(y[-1][0] - y[0][0] > x[-1][0] - x[0][0]):
p = y[0][1]; q = y[-1][1]
return (abs(P[p][0] - P[q][0]) + abs(P[p][1] - P[q][1])) // 2
need = [calc(bit) for bit in range(1 << N)]
dp = [[INF] * (1 << N) for _ in [0] * (K + 1)]
dp[0][0] = 0
for k in range(K):
for bit in range(1 << N):
bit2 = rev = ((1 << N) - 1) - bit
while(bit2):
d = max(dp[k][bit], need[bit2])
if(dp[k + 1][bit|bit2] > d):
dp[k + 1][bit|bit2] = d
bit2 = (bit2 - 1) & rev
print(dp[K][-1])
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0