結果

問題 No.1825 Except One
ユーザー LyricalMaestro
提出日時 2025-06-28 18:04:40
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,268 ms / 3,000 ms
コード長 1,274 bytes
コンパイル時間 415 ms
コンパイル使用メモリ 82,564 KB
実行使用メモリ 307,716 KB
最終ジャッジ日時 2025-06-28 18:04:50
合計ジャッジ時間 9,814 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/1825


def main():
    N = int(input())
    A = list(map(int , input().split()))

    dp = [[{} for _ in range(1)] for _ in range(1)]
    dp[0][0][0] = 1

    sum_a = 0
    for i, a in enumerate(A):
        new_dp = [[{} for _ in range(sum_a + a + 1)] for _ in range(i + 2)]

        for l in range(i + 1):
            for a0 in range(sum_a + 1):
                for max_a, value in dp[l][a0].items():

                    if max_a not in new_dp[l][a0]:
                        new_dp[l][a0][max_a] = 0
                    new_dp[l][a0][max_a] += value

                    new_max_a = max(a, max_a)
                    new_sum = a0 + a
                    if new_max_a not in new_dp[l + 1][new_sum]:
                        new_dp[l + 1][new_sum][new_max_a] = 0
                    new_dp[l + 1][new_sum][new_max_a] += value
 
        sum_a += a
        dp = new_dp
    

    answer = 0
    for l in range(2, N + 1):
        for a0 in range(sum_a + 1):
            for max_a, value in dp[l][a0].items():

                if a0 % (l - 1) != 0:
                    continue

                x = a0 // (l - 1)
                if x >= max_a:
                    answer += value
    print(answer)








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