結果

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

ソースコード

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 * 100 + 1, false)

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

0