#1158824 (Vim script) No.3509 Get More Money

• 問題: No.3509 Get More Money
• ユーザー: Nakanishi Hiro
• 提出日時: 2026-04-18 01:27:58
• 言語: Vim script (v9.2)
• 結果: TLE
• 実行時間: -
• コード長: 3,683 bytes
• コンパイル時間: 110 ms
• コンパイル使用メモリ: 6,528 KB
• 実行使用メモリ: 92,076 KB
• 最終ジャッジ日時: 2026-04-18 01:29:13
• 合計ジャッジ時間: 10,147 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_1

ファイルパターン	結果
sample	-- * 1
other	TLE * 1 -- * 59

ソースコード

vim9script

def HeapPush(heap: list<number>, value: number, is_max: bool)
  add(heap, value)
  var hp_idx = len(heap) - 1
  while hp_idx > 0
    var hp_parent = (hp_idx - 1) / 2
    if is_max
      if heap[hp_parent] >= heap[hp_idx]
        break
      endif
    else
      if heap[hp_parent] <= heap[hp_idx]
        break
      endif
    endif
    var hp_tmp = heap[hp_parent]
    heap[hp_parent] = heap[hp_idx]
    heap[hp_idx] = hp_tmp
    hp_idx = hp_parent
  endwhile
enddef

def HeapPop(heap: list<number>, is_max: bool): number
  var hp_last = remove(heap, -1)
  if empty(heap)
    return hp_last
  endif
  var hp_ret = heap[0]
  heap[0] = hp_last
  var hp_idx = 0
  var hp_n = len(heap)
  while true
    var hp_left = hp_idx * 2 + 1
    if hp_left >= hp_n
      break
    endif
    var hp_right = hp_left + 1
    var hp_child = hp_left
    if hp_right < hp_n
      if is_max
        if heap[hp_right] > heap[hp_left]
          hp_child = hp_right
        endif
      else
        if heap[hp_right] < heap[hp_left]
          hp_child = hp_right
        endif
      endif
    endif
    if is_max
      if heap[hp_idx] >= heap[hp_child]
        break
      endif
    else
      if heap[hp_idx] <= heap[hp_child]
        break
      endif
    endif
    var hp_tmp = heap[hp_idx]
    heap[hp_idx] = heap[hp_child]
    heap[hp_child] = hp_tmp
    hp_idx = hp_child
  endwhile
  return hp_ret
enddef

def HeapPeekValid(heap: list<number>, counts: dict<number>, is_max: bool): number
  while !empty(heap)
    var hp_value = heap[0]
    if get(counts, string(hp_value), 0) > 0
      return hp_value
    endif
    HeapPop(heap, is_max)
  endwhile
  return -1
enddef

def ToNumbers(line: string): list<number>
  return mapnew(split(line), (_, v) => str2nr(v))
enddef

var lines = readfile('/dev/stdin')
var idx = 0
var t = str2nr(lines[idx])
idx += 1
var out: list<string> = []

for _case in range(t)
  var header = ToNumbers(lines[idx])
  idx += 1
  var n = header[0]
  var k = header[1]
  var a = ToNumbers(lines[idx])
  idx += 1
  var b = ToNumbers(lines[idx])
  idx += 1
  var c = ToNumbers(lines[idx])
  idx += 1
  var d = ToNumbers(lines[idx])
  idx += 1

  var counts: dict<number> = {}
  var min_heap: list<number> = []
  var max_heap: list<number> = []
  var slots = 0
  var profit = 0

  for offset in range(n)
    var i = n - 1 - offset

    var sell_value = c[i]
    var sell_count = d[i]
    if sell_count > 0
      var sell_key = string(sell_value)
      counts[sell_key] = get(counts, sell_key, 0) + sell_count
      slots += sell_count
      HeapPush(min_heap, sell_value, false)
      HeapPush(max_heap, sell_value, true)
    endif

    var buy_cost = a[i]
    var remain = b[i]
    while remain > 0
      var best = HeapPeekValid(max_heap, counts, true)
      if best < 0 || best <= buy_cost
        break
      endif
      var best_key = string(best)
      var avail = counts[best_key]
      var take = avail < remain ? avail : remain
      counts[best_key] = avail - take
      slots -= take
      profit += (best - buy_cost) * take
      remain -= take

      var buy_key = string(buy_cost)
      counts[buy_key] = get(counts, buy_key, 0) + take
      slots += take
      HeapPush(min_heap, buy_cost, false)
      HeapPush(max_heap, buy_cost, true)
    endwhile

    var excess = slots - k
    while excess > 0
      var cheapest = HeapPeekValid(min_heap, counts, false)
      var cheap_key = string(cheapest)
      var avail = counts[cheap_key]
      var drop = avail < excess ? avail : excess
      counts[cheap_key] = avail - drop
      slots -= drop
      excess -= drop
    endwhile
  endfor

  add(out, string(profit))
endfor

new
setline(1, out)
:%print
qa!