結果

問題 No.1334 Multiply or Add
コンテスト
ユーザー qwewe
提出日時 2025-05-14 13:14:05
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,418 bytes
コンパイル時間 262 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 98,560 KB
最終ジャッジ日時 2025-05-14 13:15:10
合計ジャッジ時間 10,843 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50 TLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def solve():
    # Read input N
    N = int(sys.stdin.readline())
    # Read input A_1, A_2, ..., A_N
    A = list(map(int, sys.stdin.readline().split()))
    
    # Define the modulus
    MOD = 10**9 + 7

    # Initialize DP array. dp[i] will store the maximum possible value 
    # of an expression formed using the first i numbers A_1, ..., A_i.
    # dp[0] represents the base case for an empty prefix, which has value 0.
    dp = [0] * (N + 1) 

    # Iterate from i = 1 to N to compute dp[i] for each prefix length.
    for i in range(1, N + 1):
        
        # The i-th number in the sequence is A[i-1] due to 0-based indexing.
        current_num = A[i-1]

        # Optimization for A[i-1] == 1:
        # If the current number is 1, the optimal strategy is always to add it.
        # Explanation: Consider an optimal expression for A_1, ..., A_{i-1} with value V = dp[i-1].
        # We want to incorporate A_i = 1. We can either use '+' or 'x' for op_{i-1}.
        # Case 1: op_{i-1} = '+'. The expression becomes ... + 1. The value is V + 1.
        # Case 2: op_{i-1} = 'x'. Let the expression for A_1..A_{i-1} end with a block P (product).
        # The structure is ... + P. With 'x 1', it becomes ... + (P * 1) = ... + P. The value remains V.
        # Since all A_i are positive integers, V >= 1. Thus V + 1 > V.
        # So, adding 1 is always optimal or equal. We choose '+'.
        # Therefore, dp[i] = dp[i-1] + 1.
        if current_num == 1:
            dp[i] = dp[i-1] + 1
            # Skip the rest of the loop for this i and move to the next i.
            continue

        # Case: Current number A[i-1] > 1
        
        # Initialize the maximum value for dp[i].
        # One possibility is that A[i-1] forms its own block. This happens if op_{i-1} is '+'.
        # The value is dp[i-1] (max value up to A_{i-1}) + A[i-1].
        # This serves as an initial candidate for dp[i].
        current_max = dp[i-1] + current_num

        # This variable will store the product of the current block being considered, ending at A[i-1].
        # It's calculated iteratively as k decreases.
        current_prod = 1 
        
        # Iterate backwards for the start index k of the last block (A_k * ... * A_i).
        # k ranges from i down to 1.
        # The block consists of elements A[k-1], A[k], ..., A[i-1].
        for k in range(i, 0, -1):
            
            # Update the product P(k, i) = A[k-1] * ... * A[i-1].
            # In each step, multiply by A[k-1].
            # Python's arbitrary precision integers handle potentially very large products.
            current_prod = current_prod * A[k-1]
            
            # Calculate the candidate value for this choice of last block:
            # It's the maximum value using A_1...A_{k-1} (stored in dp[k-1]) 
            # plus the product P(k, i) of the last block.
            val = dp[k-1] + current_prod
            
            # Update the maximum value found so far for dp[i] if this candidate is larger.
            if val > current_max:
                current_max = val

        # After checking all possible start indices k for the last block,
        # store the computed maximum value into dp[i].
        dp[i] = current_max

    # The final answer is the maximum value using all N numbers (dp[N]),
    # taken modulo MOD.
    print(dp[N] % MOD)

# Execute the solve function
solve()
0