結果

問題 No.2520 L1 Explosion
ユーザー MasKoaTSMasKoaTS
提出日時 2022-08-23 12:41:57
言語 PyPy3
(7.3.15)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 879 bytes
コンパイル時間 170 ms
コンパイル使用メモリ 81,736 KB
実行使用メモリ 68,720 KB
最終ジャッジ日時 2023-10-25 00:36:44
合計ジャッジ時間 2,581 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
権限があれば一括ダウンロードができます

ソースコード

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