Yukicoder No.549 素材合成システム
絶対にコーナーケース埋まってるでしょと思いながらかかったが何もなかった。意外だ。
solution
最大のやつに他を全部直接合成すればよい。$O(N)$でできる。
implementation
$O(N \log N)$。
#!/usr/bin/env python3
n = int(input())
xs = sorted(map(int, input().split()))
xs, y = xs[: -1], xs[-1]
for x in xs:
y += x // 2
print(y)