結果
問題 | No.4 おもりと天秤 |
ユーザー | cm-arai |
提出日時 | 2020-12-24 15:11:50 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 76 ms / 5,000 ms |
コード長 | 955 bytes |
コンパイル時間 | 103 ms |
コンパイル使用メモリ | 12,544 KB |
実行使用メモリ | 10,752 KB |
最終ジャッジ日時 | 2024-09-21 16:55:54 |
合計ジャッジ時間 | 1,678 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 30 ms
10,624 KB |
testcase_01 | AC | 29 ms
10,752 KB |
testcase_02 | AC | 30 ms
10,752 KB |
testcase_03 | AC | 27 ms
10,624 KB |
testcase_04 | AC | 26 ms
10,752 KB |
testcase_05 | AC | 59 ms
10,624 KB |
testcase_06 | AC | 26 ms
10,624 KB |
testcase_07 | AC | 59 ms
10,752 KB |
testcase_08 | AC | 27 ms
10,624 KB |
testcase_09 | AC | 51 ms
10,624 KB |
testcase_10 | AC | 61 ms
10,624 KB |
testcase_11 | AC | 26 ms
10,624 KB |
testcase_12 | AC | 27 ms
10,624 KB |
testcase_13 | AC | 26 ms
10,624 KB |
testcase_14 | AC | 26 ms
10,624 KB |
testcase_15 | AC | 26 ms
10,752 KB |
testcase_16 | AC | 28 ms
10,624 KB |
testcase_17 | AC | 27 ms
10,624 KB |
testcase_18 | AC | 76 ms
10,752 KB |
testcase_19 | AC | 53 ms
10,624 KB |
testcase_20 | AC | 52 ms
10,752 KB |
testcase_21 | AC | 51 ms
10,624 KB |
testcase_22 | AC | 51 ms
10,752 KB |
ソースコード
N = int(input()) W = list(map(int, input().split())) # 最終的には片方の天秤に全体の半分の重さが乗る sum_weight = sum(W) / 2 # 割り切れなければ(少数を含む)天秤は釣り合わない if not sum_weight.is_integer(): print("impossible") exit(0) else: sum_weight = int(sum_weight) # 方針: 合計値だけメモっといて、そこにsum_weightが入っていれば処理終了させる # それ以外のやつは、一度処理したらスキップしたい dp = [False] * (sum_weight + 1) dp[0] = True for i in range(len(W)): for j in range(len(dp) - 1, -1, -1): if not dp[j]: continue if W[i]+j <= sum_weight: # print( # f"i={i}, j={j}, W[i]={W[i]}, dp[j]={dp[j]}, sum_weight={sum_weight}") dp[W[i] + j] = True if W[i] + j == sum_weight: print("possible") exit(0) print("impossible")