結果

問題 No.1294 マウンテン数列
ユーザー lam6er
提出日時 2025-04-09 20:56:43
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,238 bytes
コンパイル時間 492 ms
コンパイル使用メモリ 82,228 KB
実行使用メモリ 316,604 KB
最終ジャッジ日時 2025-04-09 20:58:39
合計ジャッジ時間 4,388 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 TLE * 1 -- * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    input = sys.stdin.read().split()
    N = int(input[0])
    A = list(map(int, input[1:N+1]))
    
    if N < 2:
        print(0)
        return
    
    max_val = A[-1]
    rest = A[:-1]
    if not rest:
        print(0)
        return
    
    from collections import defaultdict

    dp = defaultdict(int)
    dp[(None, None, 0, 0)] = 1

    for num in rest:
        new_dp = defaultdict(int)
        for (s_last, t_head, x_max, y_max), cnt in dp.items():
            option_add_s = False
            option_add_t = False
            if s_last is None or num > s_last:
                new_s_last = num
                if s_last is None:
                    new_x_max = 0
                else:
                    new_x = num - s_last
                    new_x_max = max(x_max, new_x)
                new_t_head = t_head
                new_y_max = y_max
                key = (new_s_last, new_t_head, new_x_max, new_y_max)
                new_dp[key] = (new_dp[key] + cnt) % MOD
                option_add_s = True
            if t_head is None or num > t_head:
                new_t_head_new = num
                if t_head is None:
                    new_y_max_new = 0
                else:
                    new_y = num - t_head
                    new_y_max_new = max(y_max, new_y)
                key = (s_last, new_t_head_new, x_max, new_y_max_new)
                new_dp[key] = (new_dp[key] + cnt) % MOD
                option_add_t = True
        dp = new_dp

    total = 0
    for (s_last, t_head, x_max, y_max), cnt in dp.items():
        x_max_total = 0
        if s_last is not None:
            x_conn = max_val - s_last
            if s_last < max_val:
                x_max_total = max(x_max, x_conn)
            else:
                x_max_total = x_max
        else:
            x_max_total = 0
        y_max_total = y_max
        conn = 0
        if t_head is not None:
            conn = max_val - t_head
        danger = max(x_max_total, y_max_total, conn)
        if (s_last is None and t_head is None) or (s_last is None and cnt == 0):
            continue
        total = (total + danger * cnt) % MOD

    print(total % MOD)

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