結果

問題 No.2840 RGB Plates
コンテスト
ユーザー navel_tos
提出日時 2026-01-27 00:56:01
言語 PyPy3
(7.3.17)
結果
AC  
実行時間 222 ms / 2,000 ms
コード長 1,391 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 354 ms
コンパイル使用メモリ 82,200 KB
実行使用メモリ 65,620 KB
最終ジャッジ日時 2026-01-27 00:56:08
合計ジャッジ時間 6,059 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#yukicoder2840 RGB Plates

#入力受取  M = max(A) とする
N: int = int(input())
A: list[int] = [int(Ai) for Ai in input().split()]
M: int = max(A)

#comb(N, k)の前計算  十分に大きくなったら打ち切り
sub: list[int] = [1] * (N + 1)
INF: int = 10 ** 9
for k in range(1, - (- N >> 1) + 1):
    sub[k] = sub[N - k] = sub[k - 1] * (N - k + 1) // k
    if sub[k - 1] >= INF or sub[k] >= INF:
        sub[k] = sub[N - k] = INF
def comb(n: int, k: int) -> int:
    assert n == N
    return sub[k] if 0 <= k <= n else 0

#N要素からk要素を選ぶ場合の数は comb(N, k) 通りある
#解の範囲は 0 <= w <= Mk 通りなので、Mk + 1 < comb(N, k) となるkがあれば解がMk以下と分かる
for k in range(1, N + 1):
    if M * k + 1 < comb(N, k):
        break
W: int = M * k

#重さW以下に絞ったナップサック問題
#DP[w]: 重さ総和がちょうどwとなるような選び方。ただし、2以上は2に丸める
DP: list[int] = [0] * (W + 1)
DP[0] = 1
for Ai in A:
    for w in range(W - Ai, -1, -1):
        DP[w + Ai] += DP[w]
        if DP[w + Ai] > 2:
            DP[w + Ai] = 2

#場合の数が2通り以上となる最小のwがあれば、G = B = w, R = sum(A) - 2w とする
ans: int = -1
for w in range(1, W + 1):
    if DP[w] >= 2:
        R: int = sum(A) - 2 * w
        if R != 0:
            ans = R
            break
print(ans)
0