結果
問題 | No.2520 L1 Explosion |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
import sysinput = sys.stdin.readlineINF = 10 ** 18N, K = map(int, input().split())P = [list(map(int, input().split())) for _ in [0] * N]def calc(bit):x = []; y = []i = 0while(bit):if(bit & 1):x.append((P[i][0] + P[i][1], i))y.append((P[i][0] - P[i][1], i))bit >>= 1i += 1if(len(x) == 0):return 0x.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])) // 2need = [calc(bit) for bit in range(1 << N)]dp = [[INF] * (1 << N) for _ in [0] * (K + 1)]dp[0][0] = 0for k in range(K):for bit in range(1 << N):bit2 = rev = ((1 << N) - 1) - bitwhile(bit2):d = max(dp[k][bit], need[bit2])if(dp[k + 1][bit|bit2] > d):dp[k + 1][bit|bit2] = dbit2 = (bit2 - 1) & revprint(dp[K][-1])