結果

問題 No.2520 L1 Explosion
ユーザー MasKoaTSMasKoaTS
提出日時 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 RE * 1 WA * 2
other RE * 1 TLE * 1 WA * 2
権限があれば一括ダウンロードができます

ソースコード

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])
0