Official
G - ご飯とパン / Rice or Bread Editorial
by
G - ご飯とパン / Rice or Bread Editorial
by
sounansya
まず、 \(1\) 日目にライスを選んだ場合奇数日目はライス、偶数日目はパンを選ぶ必要があります。 \(K\) 日間に奇数日目は \(\displaystyle \left\lfloor \frac{K+1}2\right \rfloor\) 日、偶数日目は \(\displaystyle \left\lfloor \frac{K}2\right \rfloor\) 日あるので、 \(\displaystyle N > \left\lfloor \frac{K+1}2\right \rfloor\) または \(\displaystyle M > \left\lfloor \frac{K}2\right \rfloor\) の場合は \(1\) 日目にライスを選ぶことはできません。一方、そうでない場合は \(A\) の大きい方から \(\displaystyle \left\lfloor \frac{K+1}2\right \rfloor\) 個、\(B\) の大きい方から \(\displaystyle \left\lfloor \frac{K}2\right \rfloor\) 個の総和がおいしさの総和の最大値です。
\(1\) 日目にパンを選んだ場合のおいしさの総和の最大値も同様に求めることができるので、これら \(2\) つの値の最大値が答えとなります。
実装例(Python3)
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
ans = -1
if k // 2 <= n and (k + 1) // 2 <= m:
ans = max(ans, sum(a[: k // 2]) + sum(b[: (k + 1) // 2]))
if (k + 1) // 2 <= n and k // 2 <= m:
ans = max(ans, sum(a[: (k + 1) // 2]) + sum(b[: k // 2]))
print(ans)
