結果

問題 No.269 見栄っ張りの募金活動
コンテスト
ユーザー 👑 tttmmmyyyy
提出日時 2026-11-02 22:59:54
言語 Fix
(1.6.0 + cp-library + minilib)
コンパイル:
fix_c _filename_
実行:
./a.out
結果
AC  
実行時間 10 ms / 5,000 ms
+ 69µs
コード長 1,027 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 15,444 ms
コンパイル使用メモリ 668,756 KB
実行使用メモリ 9,868 KB
最終ジャッジ日時 2026-11-02 23:00:37
合計ジャッジ時間 16,287 ms
ジャッジサーバーID
（参考情報） 		judge4_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22
権限があれば一括ダウンロードができます
コンパイルメッセージ
make: 'lib.o' は更新済みです.

ソースコード

diff #
raw source code 

module Main;

import BinaryHeap;
import BoolArray;
import CPLib.Arithmetic;
import CPLib.DSegtree;
import CPLib.Graph;
import CPLib.IO;
import CPLib.LDSegtree;
import CPLib.UnionFind;
import CPLib.ZP;
import HashMap;
import HashSet;

type Z = ZP P1000000007;

main : IO () = (
    let cN = *read_i;
    let cS = *read_i;
    let cK = *read_i;
    let cX = cS - (cN*(cN-1))/2*cK;    
    if cX < 0 { 0.to_string.println };
    let dp = fill(cN + 1, fill(cX + 1, zp(0) : Z));
    let dp = dp[0][0].iset(zp(1));
    let dp = range(1, cN+1).fold(dp, |n, dp|
        range(0, cX+1).fold(dp, |x, dp|
            let c = cN - (n - 1);
            let v = if x >= c {
                dp[n-1][x].iget + dp[n][x-c].iget
            } else {
                dp[n-1][x].iget
            };
            dp[n][x].iset(v)
            // dp[n][x] = dp[n-1][x] + dp[n-1][x-c] + dp[n-1][x-2c] + ... 
            // = dp[n-1][x] + dp[n][x-c] if x >= c,
            // = dp[n-1][x]
        )
    );
    dp[cN][cX].iget.@value.to_string.println
);
0