結果
問題 |
No.1045 直方体大学
|
ユーザー |
![]() |
提出日時 | 2020-05-02 00:25:32 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 737 ms / 2,000 ms |
コード長 | 1,094 bytes |
コンパイル時間 | 468 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 98,176 KB |
最終ジャッジ日時 | 2024-12-25 17:48:06 |
合計ジャッジ時間 | 5,646 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 17 |
ソースコード
mod = 1000000007 eps = 10**-9 inf = 10**9 def main(): import sys input = sys.stdin.readline N = int(input()) xyz = [] val = set() for i in range(N): a, b, c = map(int, input().split()) x, y, z = sorted([a, b, c]) xyz.append((x, y, z, i)) xyz.append((x, z, y, i)) xyz.append((y, z, x, i)) val.add(x) val.add(y) val.add(0) val = sorted(list(val)) val2idx = {} for i, v in enumerate(val): val2idx[v] = i xyz.sort(key=lambda p: p[0]) xyz.sort(key=lambda p: p[1]) dp = [[-inf] * (len(val)) for _ in range(2**N)] dp[0][0] = 0 for x, y, z, ii in xyz: j = val2idx[x] for state in range(2**N): if state >> ii & 1: continue for last in range(j+1): dp[state | (1 << ii)][j] = max(dp[state | (1 << ii)][j], dp[state][last] + z) ans = 0 for state in range(2**N): for last in range(len(val)): ans = max(ans, dp[state][last]) print(ans) if __name__ == '__main__': main()