結果

問題 No.4 おもりと天秤
コンテスト
ユーザー tanson
提出日時 2025-08-16 00:24:38
言語 Standard ML
(MLton 20210117)
結果
WA  
実行時間 -
コード長 1,704 bytes
コンパイル時間 6,179 ms
コンパイル使用メモリ 687,356 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-08-16 00:24:45
合計ジャッジ時間 3,961 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

fun readInt () =
    valOf (TextIO.scanStream (Int.scan StringCvt.DEC) TextIO.stdIn)


val () =
    let
        val n = readInt ()
        val ws = Array.tabulate (n, fn _ => readInt ())
        val sum = Array.foldl (fn (w, acc) => w + acc) 0 ws
        val dp = Array.array (n + 1, Array.array (100 * 100 + 100, false))

        fun doDp () =
            (Array.update (Array.sub (dp, 0), 0, true);
             Array.appi (fn (index, w) =>
                            let
                                val i = ref 0
                            in
                                if index < n
                                then
                                    (
                                      while !i < 10000 do
                                                        (if Array.sub (Array.sub (dp, index), !i) = true
                                                         then
                                                             (Array.update (Array.sub (dp, index + 1), !i + w, true);
                                                              Array.update (Array.sub (dp, index + 1), !i, true))
                                                         else ignore ();
                                                         i := !i + 1)
                                    )
                                else ignore ()
                            end
                        )
                        ws)
    in
        if sum mod 2 <> 0 then print "impossible\n"
        else
            (
              doDp ();
              if Array.sub (Array.sub (dp, n), sum div 2) = true then print "possible\n"
              else print "impossible\n"
            )
    end
0