結果

問題 No.2520 L1 Explosion
ユーザー MasKoaTS
提出日時 2022-08-23 12:41:57
言語 PyPy3
(7.3.15)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 879 bytes
コンパイル時間 294 ms
コンパイル使用メモリ 82,860 KB
実行使用メモリ 69,780 KB
最終ジャッジ日時 2024-09-24 19:38:52
合計ジャッジ時間 2,366 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 3
other RE * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline
INF = 10 ** 18

n, m = map(int, input().split())
house = [(x + y, x - y) for x,y in [map(int, input().split()) for _ in [0]*n]]

def calc_dist_max(bit):
	if(bit == 0):
		return 0
	x_max, x_min, y_max, y_min = -INF, INF, -INF, INF
	i = 0
	for i, (x,y) in enumerate(house):
		if not((bit >> i) & 1):
			continue
		if(x_max < x):
			x_max = x
		if(x_min > x):
			x_min = x
		if(y_max < y):
			y_max = y
		if(y_min > y):
			y_min = y
	return max(x_max - x_min, y_max - y_min)

req_dist = [calc_dist_max(bit) for bit in range(1 << n)]
dp = [[INF]*(1 << n) for _ in [0]*(m + 1)]
dp[0][0] = 0
for k in range(m):
	for bit in range(1 << n):
		bit2 = rev = ((1 << n) - 1) - bit
		while(bit2):
			d = max(dp[k][bit], req_dist[bit2])
			if(dp[k + 1][bit | bit2] > d):
				dp[k + 1][bit | bit2] = d
			bit2 = (bit2 - 1) & rev

ans = dp[m][-1]
print(ans)
0