結果

問題 No.90 品物の並び替え
ユーザー tanson
提出日時 2025-08-18 01:28:17
言語 Standard ML
(MLton 20210117)
結果
AC  
実行時間 177 ms / 5,000 ms
コード長 2,282 bytes
コンパイル時間 3,139 ms
コンパイル使用メモリ 689,028 KB
実行使用メモリ 127,736 KB
最終ジャッジ日時 2025-08-18 01:28:22
合計ジャッジ時間 4,259 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

fun nList 0 = [0]
  | nList n = n :: nList (n - 1)

fun insert x l =
    let
        val i = ref 0
        val generated = ref []
    in
        (
          while !i <= List.length l do
                                  (
                                    generated := (List.take (l, !i) @ (x :: (List.drop (l, !i)))) :: !generated;
                                    i := !i + 1
                                  );
          !generated
        )
    end


fun permutations nil = nil
  | permutations [x] = [[x]]
  | permutations (h::tl) = 
    let
        val perm_rest = permutations tl
        val generated = ref []
    in
        (
          List.app
              (fn ll =>
                  List.app
                      (fn lll =>
                          generated := lll :: !generated)
                      (insert h ll)
              )
              perm_rest;
          !generated
        )
    end

val () =
    let
        val n = readInt ()
        val m = readInt ()
                        
        fun makeScoreTable () =
            let
                val scores = List.tabulate (m, fn _ => (readInt (), readInt (), readInt ()))
                val table = Array.tabulate (n, fn _ => Array.array (n, 0))
            in
                (
                  List.app
                      (fn (a, b, s) =>
                          Array.update (Array.sub (table, a), b, s))
                      scores;
                  table
                )
            end

        val scoreTable = makeScoreTable ()
                                        
        val allCombinations = permutations (nList (n - 1))

        fun findScore [] = 0
          | findScore [_] = 0
          | findScore (h::tl) =
            let
                val line = Array.sub (scoreTable, h)
            in
                (List.foldl (fn (x, acc) => Array.sub (line, x) + acc) 0 tl) +
                findScore tl
            end
                
                
        val ans =
            List.foldl
                (fn (l, acc) =>
                    Int.max (findScore l, acc))
                0
                allCombinations
    in    
        print (Int.toString ans ^ "\n")
    end
0