結果

問題 No.1825 Except One
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 18:48:14
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 910 bytes
コンパイル時間 181 ms
コンパイル使用メモリ 82,244 KB
実行使用メモリ 55,216 KB
最終ジャッジ日時 2025-06-12 18:48:24
合計ジャッジ時間 4,965 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3 TLE * 1
other -- * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict

def main():
    import sys
    input = sys.stdin.read().split()
    N = int(input[0])
    A = list(map(int, input[1:N+1]))
    
    dp = defaultdict(int)
    dp[(0, 0, 0)] = 1  # (m, sum, max_e) : count
    
    for a in A:
        new_dp = defaultdict(int)
        for (m, s, e), cnt in dp.items():
            # Not take a
            new_dp[(m, s, e)] += cnt
            # Take a
            new_m = m + 1
            new_s = s + a
            new_e = max(e, a)
            new_dp[(new_m, new_s, new_e)] += cnt
        dp = new_dp
    
    total = 0
    for (m, s, e), cnt in dp.items():
        if m >= 2:
            divisor = m - 1
            if divisor == 0:
                continue
            if s % divisor == 0:
                k = s // divisor
                if k >= e:
                    total += cnt
    print(total)

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