結果
問題 | No.4 おもりと天秤 |
ユーザー | Taketo Yoshida |
提出日時 | 2020-03-11 11:33:12 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 177 ms / 5,000 ms |
コード長 | 1,712 bytes |
コンパイル時間 | 462 ms |
コンパイル使用メモリ | 86,904 KB |
実行使用メモリ | 78,844 KB |
最終ジャッジ日時 | 2023-08-10 01:20:31 |
合計ジャッジ時間 | 6,257 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 146 ms
77,940 KB |
testcase_01 | AC | 145 ms
78,032 KB |
testcase_02 | AC | 147 ms
78,536 KB |
testcase_03 | AC | 148 ms
78,548 KB |
testcase_04 | AC | 149 ms
78,556 KB |
testcase_05 | AC | 155 ms
78,676 KB |
testcase_06 | AC | 145 ms
77,960 KB |
testcase_07 | AC | 153 ms
78,844 KB |
testcase_08 | AC | 142 ms
77,732 KB |
testcase_09 | AC | 149 ms
78,720 KB |
testcase_10 | AC | 153 ms
78,748 KB |
testcase_11 | AC | 149 ms
78,188 KB |
testcase_12 | AC | 148 ms
78,024 KB |
testcase_13 | AC | 146 ms
78,060 KB |
testcase_14 | AC | 146 ms
77,956 KB |
testcase_15 | AC | 146 ms
77,952 KB |
testcase_16 | AC | 145 ms
78,252 KB |
testcase_17 | AC | 142 ms
78,180 KB |
testcase_18 | AC | 177 ms
78,672 KB |
testcase_19 | AC | 151 ms
78,612 KB |
testcase_20 | AC | 153 ms
78,292 KB |
testcase_21 | AC | 153 ms
78,512 KB |
testcase_22 | AC | 154 ms
78,532 KB |
ソースコード
from heapq import heappush, heappop, heapify from collections import deque, defaultdict, Counter import itertools from itertools import permutations, combinations, accumulate import sys import bisect import string import math import time def I(): return int(input()) def MI(): return map(int, input().split()) def S(): return input() def MS(): return map(str, input().split()) def LI(): return [int(i) for i in input().split()] def LI_(): return [int(i)-1 for i in input().split()] def StoI(): return [ord(i)-97 for i in input()] def ItoS(nn): return chr(nn+97) def input(): return sys.stdin.readline().rstrip() def show(*inp, end='\n'): if show_flg: print(*inp, end=end) def print_matrix(mat): for i in range(len(mat)): print(*mat[i]) YNL = {False: 'No', True: 'Yes'} YNU = {False: 'NO', True: 'YES'} MOD = 10**9+7 inf = float('inf') IINF = 10**10 l_alp = string.ascii_lowercase u_alp = string.ascii_uppercase ts = time.time() # sys.setrecursionlimit(10**6) nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10'] # show_flg = True show_flg = False def main(): N = I() W = LI() total = sum(W) if total % 2 == 1: print('impossible') return half = total // 2 dp = [0] * (half+1) dp[0] = 1 for i in range(N): dp_next = [0] * (half+1) dp_next[0] = 1 for j in range(half+1): if dp[j] == 1: dp_next[j] = 1 if j + W[i] <= half: dp_next[j+W[i]] = 1 # print(i, dp_next) dp = dp_next if dp[half] == 0: print('impossible') else: print('possible') if __name__ == '__main__': main()