結果

問題 No.297 カードの数式
ユーザー convexineqconvexineq
提出日時 2021-01-02 14:15:54
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 897 ms / 1,000 ms
コード長 1,201 bytes
コンパイル時間 465 ms
コンパイル使用メモリ 82,420 KB
実行使用メモリ 77,272 KB
最終ジャッジ日時 2024-04-20 08:24:20
合計ジャッジ時間 6,086 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
53,116 KB
testcase_01 AC 39 ms
53,612 KB
testcase_02 AC 40 ms
52,748 KB
testcase_03 AC 46 ms
59,424 KB
testcase_04 AC 358 ms
76,360 KB
testcase_05 AC 38 ms
52,964 KB
testcase_06 AC 40 ms
53,216 KB
testcase_07 AC 40 ms
54,264 KB
testcase_08 AC 39 ms
52,824 KB
testcase_09 AC 39 ms
53,752 KB
testcase_10 AC 40 ms
53,204 KB
testcase_11 AC 58 ms
66,020 KB
testcase_12 AC 71 ms
74,360 KB
testcase_13 AC 90 ms
76,208 KB
testcase_14 AC 84 ms
76,396 KB
testcase_15 AC 78 ms
75,356 KB
testcase_16 AC 539 ms
77,272 KB
testcase_17 AC 139 ms
76,436 KB
testcase_18 AC 897 ms
76,628 KB
testcase_19 AC 58 ms
66,652 KB
testcase_20 AC 96 ms
76,240 KB
testcase_21 AC 355 ms
76,452 KB
testcase_22 AC 239 ms
76,944 KB
testcase_23 AC 56 ms
65,200 KB
testcase_24 AC 447 ms
76,716 KB
testcase_25 AC 593 ms
77,072 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

n = int(input())
s = input().split()
INF = 1<<30
N = 1<<n
dp1 = [-INF]*N
dp2 = [INF]*N
pm = []
pmmask = 0
for i in range(n):
    if s[i].isdigit():
        dp1[1<<i] = dp2[1<<i] = int(s[i])
    else:
        pm.append(i)
        pmmask |= 1<<i
for mask in range(N):
    j = (mask-1)&mask
    while j:
        if dp1[j] != -INF and dp1[mask^j] != -INF:
            dp1[mask] = max(dp1[mask],int(str(dp1[j])+str(dp1[j^mask])))
            dp2[mask] = min(dp2[mask],int(str(dp2[j])+str(dp2[j^mask])))
        j = (j-1)&mask
for mask in range(N):
    for i in pm:
        if mask>>i&1==0: continue
        nmask = mask^(1<<i)
        j = (nmask-1)&nmask
        while j:
            if j&pmmask:
                j = (j-1)&nmask
                continue
            if dp1[j] != -INF and dp1[nmask^j] != -INF:
                if s[i] == "+":
                    dp1[mask] = max(dp1[mask],dp1[j] + dp1[nmask^j])
                    dp2[mask] = min(dp2[mask],dp2[j] + dp2[nmask^j])
                else:            
                    dp1[mask] = max(dp1[mask], -dp2[j] + dp1[nmask^j])
                    dp2[mask] = min(dp2[mask], -dp1[j] + dp2[nmask^j])
            j = (j-1)&nmask
print(dp1[-1],dp2[-1])
0