#565640 (Crystal) No.1251 絶対に間違ってはいけない最小化問題

提出ソース

結果

問題	No.1251 絶対に間違ってはいけない最小化問題
ユーザー	yuruhiya
提出日時	2020-10-10 16:26:09
言語	Crystal (1.11.2)
結果	AC
実行時間	122 ms / 2,000 ms
コード長	1,465 bytes
コンパイル時間	11,182 ms
コンパイル使用メモリ	296,484 KB
実行使用メモリ	94,376 KB
最終ジャッジ日時	2024-06-30 21:16:00
合計ジャッジ時間	27,760 ms
ジャッジサーバーID （参考情報）	judge5 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	64 ms 66,248 KB
testcase_01	AC	65 ms 66,240 KB
testcase_02	AC	64 ms 68,292 KB
testcase_03	AC	65 ms 68,288 KB
testcase_04	AC	65 ms 68,296 KB
testcase_05	AC	64 ms 66,252 KB
testcase_06	AC	65 ms 68,164 KB
testcase_07	AC	65 ms 66,124 KB
testcase_08	AC	65 ms 65,528 KB
testcase_09	AC	64 ms 65,588 KB
testcase_10	AC	64 ms 65,608 KB
testcase_11	AC	65 ms 65,532 KB
testcase_12	AC	64 ms 65,608 KB
testcase_13	AC	66 ms 65,572 KB
testcase_14	AC	64 ms 65,600 KB
testcase_15	AC	66 ms 65,544 KB
testcase_16	AC	64 ms 65,708 KB
testcase_17	AC	64 ms 65,528 KB
testcase_18	AC	111 ms 87,452 KB
testcase_19	AC	113 ms 87,260 KB
testcase_20	AC	92 ms 79,340 KB
testcase_21	AC	68 ms 67,304 KB
testcase_22	AC	98 ms 80,632 KB
testcase_23	AC	68 ms 67,652 KB
testcase_24	AC	106 ms 83,252 KB
testcase_25	AC	95 ms 82,456 KB
testcase_26	AC	76 ms 72,208 KB
testcase_27	AC	67 ms 66,844 KB
testcase_28	AC	119 ms 93,144 KB
testcase_29	AC	119 ms 86,792 KB
testcase_30	AC	120 ms 89,288 KB
testcase_31	AC	118 ms 86,836 KB
testcase_32	AC	118 ms 90,544 KB
testcase_33	AC	120 ms 86,704 KB
testcase_34	AC	121 ms 94,376 KB
testcase_35	AC	121 ms 87,552 KB
testcase_36	AC	118 ms 87,952 KB
testcase_37	AC	120 ms 90,768 KB
testcase_38	AC	118 ms 86,748 KB
testcase_39	AC	122 ms 90,720 KB
testcase_40	AC	121 ms 86,644 KB
testcase_41	AC	121 ms 94,264 KB
testcase_42	AC	122 ms 86,788 KB
testcase_43	AC	65 ms 66,372 KB
testcase_44	AC	65 ms 66,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

lib C
  fun strtoll(s : UInt8*, p : UInt8**, b : Int32) : Int64
end

class String
  def to_i64
    C.strtoll(self, nil, 10)
  end
end

class CulSum(T)
  def initialize(a : Array(T))
    @n = a.size
    @s = Array(T).new(@n + 1, T.zero)
    @n.times do |i|
      @s[i + 1] = @s[i] + a[i]
    end
  end

  def initialize(@n : Int32, &f : Int32 -> T)
    @s = Array(T).new(@n + 1, T.zero)
    @n.times do |i|
      @s[i + 1] = @s[i] + yield(i)
    end
  end

  def initialize(a, &f)
    @n = a.size
    @s = Array(T).new(@n + 1, T.zero)
    @n.times do |i|
      @s[i + 1] = @s[i] + yield(a[i])
    end
  end

  def [](l : Int32, r : Int32)
    l < r ? @s[r] - @s[l] : 0
  end

  def [](i : Int32)
    @s[i]
  end

  def [](r : Range(Int32, Int32))
    @s[r.exclusive? ? r.end : r.end + 1] - @s[r.begin]
  end

  def to_a
    (0...@n).map { |i| self[i..i] }
  end
end

n = read_line.to_i
a = read_line.split.map(&.to_i)
b = read_line.split.map(&.to_i64)

MAX_A = 2 * 10**6
c = Array(Int64).new(MAX_A + 1, 0)
n.times { |i| c[a[i] + MAX_A // 2] += b[i] }
c_sum = CulSum.new(c)

val_left = Array(Int64).new(MAX_A + 1, 0)
(1..MAX_A).each do |i|
  val_left[i] = val_left[i - 1] + c_sum[0...i]
end
val_right = Array(Int64).new(MAX_A + 1, 0)
(0...MAX_A).reverse_each do |i|
  val_right[i] = val_right[i + 1] + c_sum[i + 1..MAX_A]
end

min_val, min_index = (0..MAX_A).map { |i| val_left[i] + val_right[i] }.each_with_index.min
puts [min_index - MAX_A // 2, min_val].join(' ')

yukicoder

結果

テストケース

ソースコード