結果

問題 No.1708 Quality of Contest
ユーザー 小野寺健小野寺健
提出日時 2021-10-30 16:08:46
言語 Ruby
(3.4.1)
結果
TLE  
実行時間 -
コード長 2,388 bytes
コンパイル時間 237 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 73,252 KB
最終ジャッジ日時 2024-10-07 13:45:08
合計ジャッジ時間 5,589 ms
ジャッジサーバーID
(参考情報)
judge1 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 6 TLE * 1
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.rb:30: warning: mismatched indentations at 'end' with 'else' at 28
Main.rb:115: warning: assigned but unused variable - k
Syntax OK

ソースコード

diff #
プレゼンテーションモードにする

class PriorityQueue
def initialize(array = [])
@data = []
array.each{|a| push(a)}
end
def push(element)
@data.push(element)
bottom_up
end
def pop
if size == 0
return nil
elsif size == 1
return @data.pop
else
min = @data[0]
@data[0] = @data.pop
top_down
return min
end
end
def poll
if size == 0
return nil
else
return @data[0]
end
end
def size
@data.size
end
def data
@data
end
private
def swap(i, j)
@data[i], @data[j] = @data[j], @data[i]
end
def parent_idx(target_idx)
(target_idx - (target_idx.even? ? 2 : 1)) / 2
end
def bottom_up
target_idx = size - 1
return if target_idx == 0
parent_idx = parent_idx(target_idx)
while (@data[parent_idx][0] < @data[target_idx][0])
swap(parent_idx, target_idx)
target_idx = parent_idx
break if target_idx == 0
parent_idx = parent_idx(target_idx)
end
end
def top_down
target_idx = 0
# child
while (has_child?(target_idx))
a = left_child_idx(target_idx)
b = right_child_idx(target_idx)
if @data[b].nil?
c = a
else
c = @data[a][0] >= @data[b][0] ? a : b
end
if @data[target_idx][0] < @data[c][0]
swap(target_idx, c)
target_idx = c
else
return
end
end
end
# @param Integer
# @return Integer
def left_child_idx(idx)
(idx * 2) + 1
end
# @param Integer
# @return Integer
def right_child_idx(idx)
(idx * 2) + 2
end
# @param Integer
# @return Boolent
def has_child?(idx)
((idx * 2) + 1) < @data.size
end
end
N, M, X = gets.split(" ").map{|s| s.to_i}
A = Array.new(M) {PriorityQueue.new}
N.times {
a, b = gets.split(" ").map{|s| s.to_i}
A[b-1].push([a,b])
}
k = gets.to_i
c = gets.split(" ").map{|s| s.to_i}
cnt = []
same = PriorityQueue.new
diff = PriorityQueue.new
0.upto(M-1) {|j|
diff.push(A[j].pop) if A[j].size > 0
}
c.max.times {
sa, sb = same.size > 0 ? same.poll : [-Float::INFINITY, -1]
da, db = diff.size > 0 ? diff.poll : [-Float::INFINITY, -1]
if sa > da + X then
same.pop
ns = A[sb-1].pop
same.push(ns) if ns
cnt << sa
else
diff.pop
ns = A[db-1].pop
same.push(ns) if ns
cnt << da + X
end
}
total = 0
c.each {|i|
total += cnt[0,i].sum
}
puts total
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0