Submission #676838


Source Code Expand

Copy
let rec tabulate n f = 
  let rec loop acc m =
    if m < n then loop (f m :: acc) (m + 1)
    else List.rev acc in
  loop [] 0

let make_edge n abcs =
  let edge = Array.make n [] in
  List.iter (fun (a, b, c) ->
    edge.(a) <- (b, c) :: edge.(a)) abcs;
  edge

let rec dikjstra ( +. ) q edge d =
  match q with
  | [] -> ()
  | u :: q ->
      let u, q = 
        List.fold_left (fun (u, q') u' ->
          if d.(u) < d.(u') then (u, u' :: q') else (u', u :: q')) (u, []) q in
      List.iter (fun (v, c) ->
        d.(v) <- min d.(v) (d.(u) +. c)) edge.(u);
      dikjstra ( +. ) q edge d

let () =
  let n, m, t = Scanf.scanf "%d %d %d\n" (fun n m t -> n, m, t) in
  let as_ = Array.init n (fun _ -> Scanf.scanf "%d " (fun a -> a)) in
  let abcs = tabulate m (fun _ ->
    Scanf.scanf "%d %d %d\n" (fun a b c -> a - 1, b - 1, c)) in
  let d = Array.make n 1145141919 in
  d.(0) <- 0;
  dikjstra ( + ) (tabulate n (fun i -> i)) (make_edge n abcs) d;
  let d' = Array.make n 1145141919 in
  d'.(0) <- 0;
  dikjstra ( + ) (tabulate n (fun i -> i))
    (make_edge n (List.map (fun (a, b, c) -> (b, a, c)) abcs)) d';
  tabulate n (fun i ->
    as_.(i) * (t - d.(i) - d'.(i)))
  |> List.fold_left max 0
  |> Printf.printf "%d\n"

Submission Info

Submission Time
Task D - トレジャーハント
User fetburner
Language OCaml (4.02.3)
Score 50
Code Size 1268 Byte
Status

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 00_example_01.txt, 00_example_02.txt, 00_example_03.txt
Subtask1 50 / 50 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 50_small_01.txt, 50_small_02.txt, 50_small_03.txt, 50_small_04.txt, 50_small_05.txt, 50_small_06.txt, 50_small_07.txt, 50_small_08.txt, 50_small_09.txt, 50_small_10.txt, 60_hand_01.txt, 60_hand_02.txt, 60_hand_03.txt, 60_hand_04.txt, 70_max_01.txt, 70_max_02.txt, 70_max_03.txt
All 0 / 50 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 10_rand_01.txt, 10_rand_02.txt, 10_rand_03.txt, 10_rand_04.txt, 10_rand_05.txt, 10_rand_06.txt, 10_rand_07.txt, 10_rand_08.txt, 10_rand_09.txt, 10_rand_10.txt, 10_rand_12.txt, 10_rand_13.txt, 30_max_01.txt, 30_max_02.txt, 30_max_03.txt, 30_max_04.txt, 30_max_05.txt, 30_max_06.txt, 40_corner_01.txt, 40_corner_02.txt, 40_corner_03.txt, 40_corner_04.txt, 50_small_01.txt, 50_small_02.txt, 50_small_03.txt, 50_small_04.txt, 50_small_05.txt, 50_small_06.txt, 50_small_07.txt, 50_small_08.txt, 50_small_09.txt, 50_small_10.txt, 60_hand_01.txt, 60_hand_02.txt, 60_hand_03.txt, 60_hand_04.txt, 70_max_01.txt, 70_max_02.txt, 70_max_03.txt
Case Name Status Exec Time Memory
00_example_01.txt 4 ms 384 KB
00_example_02.txt 4 ms 384 KB
00_example_03.txt 4 ms 384 KB
10_rand_01.txt
10_rand_02.txt
10_rand_03.txt
10_rand_04.txt
10_rand_05.txt
10_rand_06.txt
10_rand_07.txt
10_rand_08.txt
10_rand_09.txt
10_rand_10.txt
10_rand_12.txt
10_rand_13.txt
30_max_01.txt
30_max_02.txt
30_max_03.txt 1562 ms 30464 KB
30_max_04.txt
30_max_05.txt
30_max_06.txt
40_corner_01.txt
40_corner_02.txt
40_corner_03.txt
40_corner_04.txt
50_small_01.txt 8 ms 1792 KB
50_small_02.txt 4 ms 512 KB
50_small_03.txt 6 ms 1152 KB
50_small_04.txt 5 ms 896 KB
50_small_05.txt 12 ms 2944 KB
50_small_06.txt 9 ms 2304 KB
50_small_07.txt 5 ms 1024 KB
50_small_08.txt 4 ms 384 KB
50_small_09.txt 6 ms 1152 KB
50_small_10.txt 5 ms 640 KB
60_hand_01.txt 4 ms 384 KB
60_hand_02.txt 4 ms 384 KB
60_hand_03.txt 4 ms 384 KB
60_hand_04.txt 4 ms 384 KB
70_max_01.txt 103 ms 11904 KB
70_max_02.txt 102 ms 11904 KB
70_max_03.txt 107 ms 11904 KB