結果

問題 No.1251 絶対に間違ってはいけない最小化問題
ユーザー yuruhiyayuruhiya
提出日時 2020-10-10 16:39:30
言語 Crystal
(1.11.2)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,430 bytes
コンパイル時間 3,083 ms
コンパイル使用メモリ 217,576 KB
最終ジャッジ日時 2024-11-14 23:51:52
合計ジャッジ時間 3,995 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
Showing last frame. Use --error-trace for full trace.

In Main.cr:40:10

 40 | self[*Indexable.range_to_index_and_count(range, @n)]
           ^
Error: splatting a union (Tuple(Int32, Int32) | Nil) is not yet supported

ソースコード

diff # 

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 [](left : Int32, count : Int32)
    @s[left + count] - @s[left]
  end

  def [](range : Range)
    self[*Indexable.range_to_index_and_count(range, @n)]
  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[..i - 1]
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..]
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(' ')
0