結果

問題 No.1334 Multiply or Add
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:15:56
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,563 bytes
コンパイル時間 536 ms
コンパイル使用メモリ 82,232 KB
実行使用メモリ 268,984 KB
最終ジャッジ日時 2025-06-12 16:17:08
合計ジャッジ時間 8,819 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 37 WA * 13 TLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

n = int(input())
A = list(map(int, input().split()))

blocks = []
current_block = 1
count_ones = 0

for num in A:
    if num == 1:
        count_ones += 1
        # If there was a current block (product >1), add it to blocks
        if current_block > 1:
            blocks.append(('block', current_block))
            current_block = 1
    else:
        if count_ones > 0:
            blocks.append(('ones', count_ones))
            count_ones = 0
        current_block *= num

# Add remaining ones or block after loop ends
if count_ones > 0:
    blocks.append(('ones', count_ones))
if current_block > 1:
    blocks.append(('block', current_block))

stack = []

for typ, val in blocks:
    if typ == 'block':
        # Try to merge with previous blocks if possible
        while len(stack) >= 2 and stack[-1][0] == 'ones':
            # Pop the 'ones' and previous block
            ones_typ, ones_count = stack.pop()
            prev_typ, prev_val = stack.pop()
            # Check if merging is better
            a = prev_val
            b = val
            k = ones_count
            if (a - 1) * (b - 1) > k + 1:
                val = a * b
            else:
                # Not better, push back and break
                stack.append((prev_typ, prev_val))
                stack.append(('ones', ones_count))
                break
        stack.append(('block', val))
    else:
        stack.append((typ, val))

# Calculate the result by summing all blocks and ones
result = 0
for typ, val in stack:
    result += val

print(result % MOD)
0