結果

問題 No.1017 Reiwa Sequence
コンテスト
ユーザー 👑 tttmmmyyyy
提出日時 2026-11-04 08:59:09
言語 Fix
(1.6.0 + cp-library + minilib)
コンパイル:
fix_c _filename_
実行:
./a.out
結果
TLE  
実行時間 -
コード長 2,541 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 13,817 ms
コンパイル使用メモリ 677,208 KB
実行使用メモリ 264,824 KB
最終ジャッジ日時 2026-11-04 08:59:45
合計ジャッジ時間 32,787 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge4_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 7 TLE * 2 -- * 42
権限があれば一括ダウンロードができます
コンパイルメッセージ
make: 'lib.o' は更新済みです.

ソースコード

diff #
raw source code 

module Main;

// import BinaryHeap;
import BoolArray;
// import CPLib.Arithmetic;
// import CPLib.Bipartite;
// import CPLib.Bits;
// import CPLib.Convolution;
// import CPLib.DSegtree;
// import CPLib.Graph;
import CPLib.IO;
// import CPLib.LDSegtree;
// import CPLib.LSegtree;
// import CPLib.MaxFlow;
// import CPLib.Memoize;
// import CPLib.MinCostFlow;
// import CPLib.Misc;
// import CPLib.Monoid;
// import CPLib.Segtree;
// import CPLib.String;
// import CPLib.Trait;
// import CPLib.TwoSat;
// import CPLib.UnionFind;
// import CPLib.ZP;
// import HashMap;
// import HashSet;

cM : I64 = 150000;


main : IO () = (
    let iN = *read_i;
    let iAs = *read_is(iN);
    let cI = (
        count_up(1).filter(|n|
            1.shift_left(n)-1 > iAs.to_iter.sum
        ).get_first.as_some
    );
    let cL = min(cI, iN);
    let as = iAs.get_sub(0, cL);
    let mx = iAs.to_iter.sum * as.@size;
    // let dp = fill(2, fill(as.@size + 1, fill(2 * mx + 1, false)));
    let dp = fill(2, fill(as.@size + 1, BoolArray::make(2*mx + 1)));
    // let dp = dp[0][0][0 + mx].iset(true);
    let dp = dp[0][0].imod(set(mx, true));
    let (dp, last) = range(0, as.@size).fold((dp, as.@size), |n, (dp, last)|
        if dp[1][n].iget.@(mx) {
            let last = n;
            (dp, last)
        };
        let dp = range(0, 2).fold(dp, |nz, dp|
            range(0, 2 * mx + 1).fold(dp, |sum_i, dp|
                if !dp[nz][n].iget.@(sum_i) { dp };
                range(0, 3).fold(dp, |x_i, dp|
                    let x = x_i - 1;
                    let sum_i = sum_i + x * as.@(n);
                    let nz = nz == 1 || x != 0;
                    let nz = if nz { 1 } else { 0 };
                    dp[nz][n+1].imod(set(sum_i, true))
                )
            )
        );
        (dp, last)
    );
    if !dp[1][last].iget.@(mx) { println("No") };
    let (xs, _, _) = range_step(last, 0, -1).fold(([], 1, mx), |n, (xs, nz, v)|
        // dp[nz][n][v] == true
        let a = as.@(n-1);
        let (prev_nz, x) = range(0, 2).product(range(0, 3)).map(|(prev_nz, x)| (prev_nz, x - 1)).filter(|(prev_nz, x)|
            dp[prev_nz][n-1].iget.@(v + x * a) && (nz == 0 || prev_nz == 1 || x != 0)
        ).get_first.as_some;
        let prev_v = v + x * a;
        let xs = xs.push_back(x);
        (xs, prev_nz, prev_v)
    );
    let xs = xs.reverse;
    let ans = range(0, last).map(|i| as.@(i) * xs.@(i)).to_array + fill(iN - last, 0);
    println("Yes");;
    "{}".printfln((ans.to_iter.joined_with(" "),));;
    pure()
);
0