結果

問題 No.1334 Multiply or Add
ユーザー lam6er
提出日時 2025-04-16 16:02:45
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,601 bytes
コンパイル時間 417 ms
コンパイル使用メモリ 81,696 KB
実行使用メモリ 105,600 KB
最終ジャッジ日時 2025-04-16 16:09:08
合計ジャッジ時間 6,902 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 58 WA * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

def main():
    import sys
    input = sys.stdin.read().split()
    n = int(input[0])
    a = list(map(int, input[1:n+1]))
    
    elements = []
    i = 0
    while i < n:
        if a[i] == 1:
            count = 0
            while i < n and a[i] == 1:
                count += 1
                i += 1
            elements.append(('1-group', count))
        else:
            product = 1
            while i < n and a[i] != 1:
                product = (product * a[i]) % MOD
                i += 1
            elements.append(('run', product))
    
    stack = []
    for elem in elements:
        if elem[0] == 'run':
            current_run = elem[1]
            while True:
                if len(stack) >= 2 and stack[-2][0] == 'run' and stack[-1][0] == '1-group':
                    prev_run = stack[-2][1]
                    k = stack[-1][1]
                    merged_run = (prev_run * current_run) % MOD
                    original_sum = (prev_run + k + current_run) % MOD
                    if merged_run > original_sum:
                        stack.pop()
                        stack.pop()
                        current_run = merged_run
                    else:
                        break
                else:
                    break
            stack.append(('run', current_run))
        else:
            stack.append(elem)
    
    total = 0
    for elem in stack:
        if elem[0] == 'run':
            total = (total + elem[1]) % MOD
        else:
            total = (total + elem[1]) % MOD
    print(total)

if __name__ == '__main__':
    main()
0