結果
問題 |
No.4 おもりと天秤
|
ユーザー |
|
提出日時 | 2021-03-11 07:40:26 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 63 ms / 5,000 ms |
コード長 | 654 bytes |
コンパイル時間 | 159 ms |
コンパイル使用メモリ | 81,836 KB |
実行使用メモリ | 65,280 KB |
最終ジャッジ日時 | 2024-10-12 22:05:47 |
合計ジャッジ時間 | 2,218 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
from collections import Counter n = int(input()) W = list(map(int,input().split())) sm = sum(W) if sm%2: print('impossible') exit() cnt = Counter(W) keys = sorted(cnt.keys()) #print(keys) dp = [[-1]*(sm//2+1) for _ in range(len(keys)+1)] dp[0][0] = 0 for i in range(1,len(keys)+1): for s in range(sm//2+1): if dp[i-1][s] >= 0:#和sがi番目までで作れてるとき dp[i][s] = cnt[keys[i-1]] elif s-keys[i-1] >= 0 and dp[i][s-keys[i-1]] >= 1: dp[i][s] = dp[i][s-keys[i-1]] - 1 else: dp[i][s] = -1 #print(dp) print("possible" if dp[len(keys)][sm//2] >= 0 else "impossible")