結果

問題 No.4 おもりと天秤
ユーザー tanson
提出日時 2025-08-16 00:19:18
言語 Standard ML
(MLton 20210117)
結果
RE  
実行時間 -
コード長 1,452 bytes
コンパイル時間 4,028 ms
コンパイル使用メモリ 688,000 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-08-16 00:19:26
合計ジャッジ時間 5,396 ms
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 12 WA * 3 RE * 8
権限があれば一括ダウンロードができます

ソースコード

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
                                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)
                            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